学步园

题意：给字符串S，T，找到所有的tetrad (a,b,c,d)， Sa..b + Sc..d = T , a≤b and c≤d.也就是把T分成两段，这两段都由S中的子串组成的，求有多少中组合方式（S中的两个子串可重叠）

这题纠结了很长时间，看了这个之后才发现自己的思路漏了一种情况（代码中注释的部分）：【ZOJ3587】Marlon's String

网上还有人用exKMP做的 zoj 3587 Marlon's String(拓展KMP+dp)

关于代码中注释部分的解释：用cnt[i]记录一个前缀的出现次数，最后统计cnt[next[i]]+=cnt[i]。因为如果前缀j能在i这个位置出现一次那么next[j]一定能在i这个位置出现一次。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100005;

char ss[N],tt[N];
int next[N],cnt1[N],cnt2[N];
int len1,len2;

void getNext (char s[],int len)  
{  
    next[0]=-1;  
    int i=0,j=-1;  
    while (i<len)  
    {  
        if (j==-1 || s[i]==s[j])  
            next[++i]=++j;
        else j=next[j];
    }  
} 

void KMP (int *cnt)
{
	int i=0,j=0;
	while (i<len1)
		if (j == -1 || ss[i] == tt[j])
			i++,j++,cnt[j]++;
		else
			j=next[j];
	for (i=len2;i>=0;i--) //很重要,注意理解
		if (next[i] != -1)
			cnt[next[i]] += cnt[i];
}

void reverse (char *str)
{
	int len = strlen(str);
	for (int i=0;i<len/2;i++)
		swap (str[i],str[len-i-1]);
}

int main ()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%s%s",ss,tt);
		len1 = strlen(ss);
		len2 = strlen(tt);
		memset(cnt1,0,sizeof(cnt1));
		memset(cnt2,0,sizeof(cnt2));
		getNext (tt,len2);
		KMP(cnt1);
		reverse(ss);
		reverse(tt);
		getNext(tt,len2);
		KMP(cnt2);
		long long ans = 0;
		for (int i=1;i<len2;i++)
			ans += (long long)cnt1[i] * cnt2[len2-i];
		printf("%lld\n",ans);
	}
	return 0;
}