Zoj 3587 Marlon's String (KMP 字符串拼接前缀出现次数)

红太狼 2022-08-23 12:58 8阅读 0赞

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

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

网上还有人用exKMP做的 [zoj 3587 Marlon's String(拓展KMP+dp)][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;
    }

[ZOJ3587_Marlon_s String]: http://blog.csdn.net/c0de4fun/article/details/7883301
[zoj 3587 Marlon_s String_KMP_dp]: http://www.2cto.com/kf/201211/165112.html