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:
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.
此题两种DP方式。
先预处理出来b串在a串中匹配的位置,然后开始DP。
设$f[i]$表示考虑到$i$位置,且$i$的最后一个字符串与b串是匹配的方案数。
显然如果$i$不是b的匹配位置,$f[i]=f[i-1]$。
如果$i$是b的匹配位置,首先考虑只有一个串, 那么答案就是$i-lb+1$,因为$1$到$i-lb+1$的所有位置都可以作为一个开始。
那如果是多个串呢?如果我们设最后一个串从位置$k$开始,那么前面的所有的方案数就是$\large \sum_{i=1}^{k}f[i]$,对于每个位置k求和,就是$\large \sum_{k=1}^{i-lb} \sum_{j=1}^{k} f[j]$。
这样只用记录一下f的前缀和和f的前缀和的前缀和就可以快速转移啦。
代码在后面贴。
还有一种方法,状态的定义略微的有些不同,设$f[i]$表示,到第i个位置之前总共有多少方案,其实就是前缀和了一下。
每次记录上一个匹配点,从上一个匹配点开始转移。
代码贴后面了。
找匹配点可以用kmp,或者hash都行。
方法1:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define reg register
#define mod 1000000007
int la, lb;
char a[], b[];
unsigned long long hsha[], hshb[], fac[];
bool End[];
int f[], sum[], Ssum[];
int ans;int main()
{
scanf("%s%s", a + , b + );
la = strlen(a + ), lb = strlen(b + );
for (reg int i = ; i <= la ; i ++) hsha[i] = hsha[i - ] * + (a[i] - 'a' + );
for (reg int i = ; i <= lb ; i ++) hshb[i] = hshb[i - ] * + (b[i] - 'a' + );
fac[] = ;
for (reg int i = ; i <= max(la, lb) ; i ++) fac[i] = fac[i - ] * ;
for (reg int i = lb ; i <= la ; i ++)
if (hsha[i] - hsha[i - lb] * fac[lb] == hshb[lb]) End[i] = ;
for (reg int i = ; i <= la ; i ++)
{
if (!End[i]) f[i] = f[i-];
else f[i] = Ssum[i - lb] + i - lb + ;
sum[i] = sum[i-] + f[i];if(sum[i] >= mod) sum[i] -= mod;
Ssum[i] = Ssum[i-] + sum[i];if(Ssum[i] >= mod) Ssum[i] -= mod;
}
for (reg int i = ; i <= la ; i ++)
ans = (ans + f[i]) % mod;
cout << ans << endl;
return ;
}
方法2:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define reg register
#define mod 1000000007
int la, lb;
char a[], b[];
int nxt[];
bool End[];
int f[], sum[];int main()
{
scanf("%s%s", a + , b + );
la = strlen(a + ), lb = strlen(b + );
int k = ;
for (reg int i = ; i <= lb ; i ++)
{
while(k and b[i] != b[k + ]) k = nxt[k];
if (b[k + ] == b[i]) k ++;
nxt[i] = k;
}
k = ;
for (reg int i = ; i <= la ; i ++)
{
while(k and a[i] != b[k + ]) k = nxt[k];
if (b[k + ] == a[i]) k ++;
if (k == lb) End[i] = ;
}
int lst = -;
for (reg int i = ; i <= la ; i ++)
{
f[i] += f[i-];
if (End[i]) lst = i - lb + ;
if (lst != -) f[i] += sum[lst - ] + lst;
if (f[i] >= mod) f[i] -= mod;
sum[i] = sum[i-] + f[i];
if (sum[i] >= mod) sum[i] -= mod;
}
cout << f[la] << endl;
return ;
}