题意： 给两个串S,T，问能找出多少的S的(a1,b1)(a2,b2)..(ak,bk)，使Sa1---Sb1,...Sak---Sbk都包含子串T，其中k>=1,且(a1,b1)...(ak,bk)互不相交。
比如S = "abacaba",T="aba", 当k=1时，(0,6)满足，还有其他只包含一个aba串的也满足，k-2时，(0,2)(3,6)满足，(0,2)(4,6)也满足，(0,3)(4,6)也满足，所以总共有12种。
解法：dp.先用kmp找出所有匹配点。
定义dp[i] = bn为 i 的方法数(尾部为 i )。
则转移方程： 如果 i 是某匹配的尾字母时，
左边意味着取的区间数K>1的情况，第一个循环枚举ak,第二个循环枚举b(k-1)， 右边意味着取得区间数为1，即就取一个区间的方式数（为从左边取起，取到此时匹配串的第一个字母为止）
否则 dp[i] = dp[i-1]
于是，我们可以维护 
, 再维护
那么sum[i] = sum[i-1]+ans[i], ans[i] = ans[i-1]+dp[i];
（感谢God yue 提供思路）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
#define lll __int64
using namespace std;
#define N 100007 char S[N],T[N];
int next[N],flag[N],n,m; void getnext(char* b) {
int i = ,j = next[] = -;
while(i < m) {
if(j == - || b[i] == b[j]) next[++i] = ++j;
else j = next[j];
}
} void kmp(char* a,char *b){
memset(flag,,sizeof(flag));
int i = -,j = -;
while(i < n && j < m) {
if(j == - || a[i] == b[j]) i++,j++;
else j = next[j];
if(j == m) {
flag[i] = ;
j = next[j];
}
}
} lll dp[N],ans[N],sum[N]; int main()
{
int i,j;
scanf("%s%s",S,T);
n = strlen(S), m = strlen(T);
getnext(T);
kmp(S,T);
dp[] = ans[] = sum[] = ;
for(i=;i<=n;i++)
{
if(!flag[i]) dp[i] = dp[i-];
else dp[i] = (sum[i-m]+i-m+)%Mod;
ans[i] = (ans[i-] + dp[i])%Mod;
sum[i] = (sum[i-] + ans[i])%Mod;
}
cout<<ans[n]<<endl;
return ;
}