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

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

红太狼 2022-08-23 12:58 69阅读 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

网上还有人用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;
}