# [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 109 + 7.

## 输入格式 InputFormat

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

## 输出格式 OutputFormat

Print the answer in a single line.

## 样例输入 SampleInput

welcometoroundtwohundredandeightytwo
d

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;
}