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());
    }
}