[Codeforces494B] Obsessive String

描述 Description

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

\[\forall i(1 \leq i \leq k) \ 1 \leq a_i,b_i \leq |s|\]

\[\forall i(1 \leq i \leq k) \ b_i \geq a_i\]

\[\forall i(2 \leq i \leq k) \ a_i > b_{i-1}\]

\[\forall i(1 \leq i \leq k)\] 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 10⁹ + 7.

输入格式 InputFormat

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

输出格式 OutputFormat

Print the answer in a single line.

样例输入 SampleInput

welcometoroundtwohundredandeightytwo
d

样例输出 SampleOutput

274201

Codeforces 494B

代码 Code

kmp 预处理出 s[i] 结尾的字符串是否是 t，f[i] 表示前 i 个字符、最后一个字符串以 s[i] 结尾的方案数，g[i] 表示前 i 个字符的方案数（即 f[i] 前缀和），sum[i] 表示 g[i] 前缀和。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=100005;
const int mod=1000000007;
int i,j,n,m,l,r,k,z,y,x;
char s[maxn],t[maxn];
bool b[maxn];
int pre[maxn],f[maxn],g[maxn],sum[maxn];
inline void kmp()
{
    int i,j,k;
    memset(b,false,sizeof(b));
    pre[1]=j=0;
    for (i=2;i<=m;i++)
    {
        while (j>0 && t[j+1]!=t[i]) j=pre[j];
        if (t[j+1]==t[i]) j++;
        pre[i]=j;
    }
    j=0;
    for (i=1;i<=n;i++)
    {
        while (j>0 && t[j+1]!=s[i]) j=pre[j];
        if (t[j+1]==s[i]) j++;
        if (j==m) b[i]=true;
    }
}
int main()
{
    scanf("%s%s",s+1,t+1);
    n=strlen(s+1);m=strlen(t+1);
    kmp();
    for (i=1;i<=n;i++)
    {
        if (!b[i])
        {
            f[i]=f[i-1];
            g[i]=(g[i-1]+f[i])%mod;
            sum[i]=(sum[i-1]+g[i])%mod;
        }
        else
        {
            f[i]=sum[i-m]+i-m+1;
            g[i]=(g[i-1]+f[i])%mod;
            sum[i]=(sum[i-1]+g[i])%mod;
        }
    }
    printf("%d\n",g[n]);
    return 0;
}