CF163A.Substring and Subsequence
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
One day Polycarpus got hold of two non-empty strings s and t , consisting of lowercase Latin letters. Polycarpus is quite good with strings, so he immediately wondered, how many different pairs of " x y " are there, such that x is a substring of string s , y is a subsequence of string t , and the content of x and y is the same. Two pairs are considered different, if they contain different substrings of string s or different subsequences of string t . Read the whole statement to understand the definition of different substrings and subsequences.
The length of string s is the number of characters in it. If we denote the length of the string s as ∣s∣ , we can write the string as s=s1s2... s∣s∣ .
A substring of s is a non-empty string x=s[a... b]=sasa+1... sb ( 1<=a<=b<=∣s∣ ). For example, "code" and "force" are substrings or "codeforces", while "coders" is not. Two substrings s[a... b] and s[c... d] are considered to be different if a=c or b=d . For example, if s ="codeforces", s[2...2] and s[6...6] are different, though their content is the same.
A subsequence of s is a non-empty string y=s[p1p2... p∣y∣]=sp1sp2... sp∣y∣ ( 1<=p_{1}<p_{2}<...<p_{|y|}<=|s| ). For example, "coders" is a subsequence of "codeforces". Two subsequences u=s[p1p2... p∣u∣] and v=s[q1q2... q∣v∣] are considered different if the sequences p and q are different.
输入格式
The input consists of two lines. The first of them contains s ( 1<=∣s∣<=5000 ), and the second one contains t ( 1<=∣t∣<=5000 ). Both strings consist of lowercase Latin letters.
输出格式
Print a single number — the number of different pairs " x y " such that x is a substring of string s , y is a subsequence of string t , and the content of x and y is the same. As the answer can be rather large, print it modulo 1000000007 (109+7) .
输入输出样例
输入#1
aa aa
输出#1
5
输入#2
codeforces forceofcode
输出#2
60
说明/提示
Let's write down all pairs " x y " that form the answer in the first sample: " s[1...1] t[1] ", " s[2...2] t[1] ", " s[1...1] t[2] "," s[2...2] t[2] ", " s[1...2] t[1 2] ".