Codeforces 494B. Obsessive String KMP+DP

dp[i]表示到第i個可以分的段數,dp[i]=dp[i-1]+ ( dp[j]+1 ) ( 0<=j<=near[i] ) near[i]是距離i最靠右的一個含有T串的位置

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.

Sample test(s) input

ababa
aba
      

output

5
      

input

welcometoroundtwohundredandeightytwo
d
      

output

274201
      

input

ddd
d
      

output

12      

/* ***********************************************
Author        :CKboss
Created Time  :2015年03月20日 星期五 19時30分59秒
File Name     :CF494B.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int maxn=100100;
const int mod=1e9+7;

char s[maxn],t[maxn];
int fail[maxn];
int near[maxn];
int dp[maxn],sum[maxn];

void getfail(char* p,int* f)
{
	int m=strlen(p);
	f[0]=f[1]=0;
	for(int i=1;i<m;i++)
	{
		int j=f[i];
		while(j&&p[j]!=p[i]) j=f[j];
		f[i+1]=(p[i]==p[j])?j+1:0;
	}
}

void kmp(char* t,char* p,int* f)
{
	int n=strlen(t),m=strlen(p);
	getfail(p,f);
	int j=0;
	for(int i=0;i<n;i++)
	{
		while(j&&p[j]!=t[i]) j=f[j];
		if(p[j]==t[i]) j++;
		if(j==m) { near[i+1]=i-m+2; j=f[j]; }
	}
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	scanf("%s",s); scanf("%s",t);

	kmp(s,t,fail);
	int n=strlen(s),m=strlen(t);

	for(int i=1;i<=n;i++)
		if(near[i]==0) near[i]=near[i-1];

	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1];
		if(near[i])
		{
			dp[i]=(dp[i]+sum[near[i]-1]+near[i])%mod;
		}
		sum[i]=(sum[i-1]+dp[i])%mod;
	}
	printf("%d\n",dp[n]);
    
    return 0;
}