zoj 3587 蛮好的KMP题
我以前做过的KMP http://www.cnblogs.com/wuyiqi/tag/KMP/
题意：从S串中拿出两个子串能拼成T串的方案有多少种，两个子串可以重复
这道题其实要解决的问题就是求T串的某个前缀在S串中出现了几次(cnt[]) 以及T串的某个后缀在S串中出现了几次(cnt2[])，那么答案就是cnt[i]*cnt2[len-i]的和
具体求的过程就很简单了，cnt[next[i]]+=cnt[i]即可，最后的cnt[i]就表示了i前缀出现的次数，后缀的话将字符串反转再KMP即可
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long lld;const int maxn = 100001;int n,m;char a[maxn],b[maxn];int p[maxn],cnt[maxn],cnt2[maxn];void getp(){ p[1]=0; int i,j=0; for(i=2;i<=m;i++){ while(j>0&&b[j+1]!=b[i]) j=p[j]; if(b[j+1]==b[i]) j+=1; p[i]=j; }}void kmp(int cnt[]){ int i,j=0; for(i=1;i<=n;i++){ while(j>0&&b[j+1]!=a[i]) j=p[j]; if(b[j+1]==a[i]) j+=1,cnt[j]++; if(j==m) j=p[j]; }for(i=m;i>=1;i--){if(p[i]!=0) cnt[p[i]]+=cnt[i];}}void RE(char s[]){int len=strlen(s+1);for(int i=1;i<=len/2;i++){swap(s[i],s[len-i+1]);}}lld solve(){lld ans=0;for(int i=1;i<=m;i++)ans+=(lld)cnt[i]*cnt2[m-i];return ans;}int main(){int t;scanf("%d",&t);while(t--) {scanf("%s",a+1);scanf("%s",b+1); m=strlen(b+1); n=strlen(a+1);memset(cnt,0,sizeof(cnt)); getp(); kmp(cnt);RE(a);RE(b);memset(cnt2,0,sizeof(cnt2));getp();kmp(cnt2);printf("%lld\n",solve()); }}