题意： 给两个串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 = 0,j = next[0] = -1; while(i < m) { if(j == -1 || b[i] == b[j]) next[++i] = ++j; else j = next[j]; } } void kmp(char* a,char *b){ memset(flag,0,sizeof(flag)); int i = -1,j = -1; while(i < n && j < m) { if(j == -1 || a[i] == b[j]) i++,j++; else j = next[j]; if(j == m) { flag[i] = 1; 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[0] = ans[0] = sum[0] = 0; for(i=1;i<=n;i++) { if(!flag[i]) dp[i] = dp[i-1]; else dp[i] = (sum[i-m]+i-m+1)%Mod; ans[i] = (ans[i-1] + dp[i])%Mod; sum[i] = (sum[i-1] + ans[i])%Mod; } cout<<ans[n]<<endl; return 0; }