cf494b kmp&&dp

http://www.elijahqi.win/archives/487

B. Obsessive String

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Hamed has recently found a string t and suddenly became quite fond of it. He spent several days trying to find all occurrences of t in other strings he had. Finally he became tired and started thinking about the following problem. Given a string s how many ways are there to extract k ≥ 1 non-overlapping substrings from it such that each of them contains string t as a substring? More formally, you need to calculate the number of ways to choose two sequences a1, a2, …, ak and b1, b2, …, bk satisfying the following requirements:

k ≥ 1

t is a substring of string saisai + 1… sbi (string s is considered as 1-indexed).

As the number of ways can be rather large print it modulo 109 + 7.

Input

Input consists of two lines containing strings s and t (1 ≤ |s|, |t| ≤ 105). Each string consists of lowercase Latin letters.

Output

Print the answer in a single line.

Examples

Input

ababa

aba

Output

5

Input

welcometoroundtwohundredandeightytwo

d

Output

274201

Input

ddd

d

Output

12

這題今晚寫的有點神志不清了，明天還得搭乘航班飛往胡志明，先留坑，明早填坑的。

滿足以下條件

1、集合中的所有串都是s的子串，且互不重疊 2、集合中的所有串都含有子串t。

設串s長度為n，串t長度為m，我們首先用kmp在s中比對t，比對成功的位置我們打下标記flag[i]=1(s[i-m+1…i]=t[1..m]).

設f[i]表示在s中以i結尾的集合數目,sum1[i]為fp[1..i]得字首和，sum2[i]為sum1[1..i]得字首和。如果flag[i]為0，則f[i]=f[i-1]。如果flag[i]為1，則dp[i]=i-m+1+sum2[i-m]。證明：若flag[i]=1，說明s[i-m+1…i]=t[1..m]，那麼sj..i都含有子串t，如果集合中隻有一個串的話，一共有i-m+1種，如果在集合中有兩個以上比對的，那麼假設我們選擇其中一個串，能和他比對的串，因為不能重疊，是以是f[1]+f[2]+..+f[j-1]即sum1[j-1]，那麼所有的可能就是sum1[1]+sum1[2]…+sum1[i-m]，即sum2[i-m]。是以f[i]=i-m+1+sum2[i-m]

解釋一下這個推導過程，大概就是多個完全比對的時候，那麼目前這個，同若隻有一個的時候i-m+1

然後前面每個完全比對的就由sum2提供，在紙上畫一下 假設一個s串，然後t在其中有三個比對的，然後就可以明白了

http://blog.csdn.net/icefox_zhx/article/details/76038942

#include<cstdio>
#include<cstring>
#define mod 1000000007
#define N 100100
bool flag[N];
int f[N],sum1[N],sum2[N],next[N];
char s[N],t[N];
long long ans;
int main(){
    freopen("cf494b.in","r",stdin);
//  freopen("cf494b.out","w",stdout);
    scanf("%s%s",s+,t);
    int i=,j=-,n=strlen(t);next[]=-;
    while (i<n){
        if (j==-||t[i]==t[j]){
            ++i;++j;next[i]=j;
        }else j=next[j];
    }
    for (int i=n;i>=;--i) t[i]=t[i-];
    int m=strlen(s+);int k=;
    for (int i=;i<=m;++i){
        while (k&&s[i]!=t[k+]) k=next[k];
        if (t[k+]==s[i])++k;
        if (k==n) flag[i]=true;
    }
    for (int i=;i<=m;++i){
        if (flag[i]){
            (f[i]=i-n++sum2[i-n])%=mod;
        }else f[i]=f[i-];
        sum1[i]=(sum1[i-]+f[i])%mod;
        sum2[i]=(sum2[i-]+sum1[i])%mod;
    }
    for (int i=;i<=m;++i) (ans+=f[i])%=mod;
    printf("%d",ans);
    return ;
}