题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6153
扩展kmp不理解的看下：http://www.cnblogs.com/z1141000271/p/7404717.html
大致题意：给定一个a串作为 母串，然后b作为模式串，
f【i】 为b的后缀的长度。
d[i] 为b这个后缀在 a串中出现的次数。。
问你他们的 积是多少，积mod1e9+7
题解：赛后补题目的时候，看到大佬用扩展kmp解，就去看了下扩展kmp,然后把第一个输入的字符串当t,第二个输入的字符串当s，然后卡了一天。
无奈又去看了下大佬的题解，原来是把第二个串当t串，那么怎么解决次数问题呢。我们把两个串倒置一下，用s去匹配t（倒置后）比如 s=aabaaba t=aab 倒置之后 s1=abaabaa
t1=baa。那么extend[1]=3,extend[4]=3。那问题来了，这个求出来有什么用呢？我要求的是t的后缀在s中出现的次数，那倒置之后，是不是如果长度大的出现过了，长度小的一定会出现一次。然后用一个等差公式计数就可以了。。 服气服气。终于补完这道题目了。。。
ac代码(略丑)：
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #define mt(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const ll mod=1e9+7; ll extend[1000001]; ll Next[1000001]; ll min(ll x,ll y) { if(x>y) return y; return x; } void getNext(string t) { mt(Next); ll len=t.length(); Next[0]=len; ll a,p; a=1; while( a<len && t[a]==t[a-1]) a++; Next[1]=a-1; a=1; for(ll i=2;i<len;i++) { p=a+Next[a]-1; if((i-1)+Next[i-a] < p ) Next[i]=Next[i-a]; else { ll j = (p - i + 1) > 0 ? (p - i + 1) : 0; while(i + j < len && t[i+j] == t[j]) j++; Next[i]=j; a=i; } } } void exkmp(string s,string t) // t->next s->extend { getNext(t); ll a,p;// ll slen=s.length(); ll tlen=t.length(); a=p=0; ll len=min(s.length(),t.length()); while(p<len && t[p]==s[p]) p++; // after extend[0]=p; for(ll i=1;i<slen;i++) { p=a+extend[a]-1; // update if( (i-1)+Next[i-a] < p) extend[i]=Next[i-a]; else { ll j = (p - i + 1) > 0 ? (p - i + 1) : 0; while( j < tlen && i+j < slen && s[i + j] == t[j]) j++; extend[i]=j; a=i; } } } int main() { string s,t;// s->exkmp t->Next int Case; scanf("%d",&Case); while(Case--) { cin>>s>>t; reverse(s.begin(),s.end()); reverse(t.begin(),t.end()); exkmp(s,t); ll ans=0; int len=s.size(); for(int i=0;i<len;i++) { ans=(ans+extend[i]*(extend[i]+1LL)/(2LL))%mod; } cout<<ans<<endl; } return 0; }
这个包含的关系要理清楚——匹配长度较大的成立，长度小的也成立。