Codeforces 149E Martian Strings（Z-Box or kmp）

秒速五厘米 2021-10-18 09:34 276阅读 0赞

## 题意：给定一个文本串和多个模式串，问有多少个串能被拆分成恰好两段被匹配到。   分析：比较容易想到的一个题，就当练一下Z-Box。对于每一个模式串，将文本串接在模式串后面，处理出新串的z数组。数组pos\[i\]表示模式串长度为i的前缀最小被匹配到的位置。然后把模式串和文本串分别反过来，再次匹配，匹配到长度为len-i时判断是否合法即可。参考https://blog.csdn.net/szh\_0808/article/details/79257961。   代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define inf 0x3f
    const int MAXN=200010;
    const int MAXM=1010;
    char s[MAXN],c[MAXN],S[MAXN];
    int z[MAXN],N,pos[MAXM],n,len,tot;
    
    void get_z()
    {
        int l=0,r=0;
        for (int i=1;i<=n+len;i++)
        {
            if (i>r)
            {
                l=i,r=i;
                while (r<n+len && s[r]==s[r-l]) r++;
                z[i]=r-l,r--;
            }
            else
            {
                int k=i-l;
                if (z[k]<r-i+1) z[i]=z[k];
                else
                {
                    l=i;
                    while (r<n+len && s[r]==s[r-l]) r++;
                    z[i]=r-l,r--;
                }
            }
            if (i>len && z[i]) pos[z[i]]=min(pos[z[i]],i-len+z[i]-1);
        }
    }
    
    void get_Z()
    {
        int l=0,r=0;
        for (int i=1;i<=n+len;i++)
        {
            if (i>r)
            {
                l=i,r=i;
                while (r<n+len && S[r]==S[r-l]) r++;
                z[i]=r-l,r--;
            }
            else
            {
                int k=i-l;
                if (z[k]<r-i+1) z[i]=z[k];
                else
                {
                    l=i;
                    while (r<n+len && S[r]==S[r-l]) r++;
                    z[i]=r-l,r--;
                }
            }
            if (i>len) if (pos[len-z[i]]<=n+len-i-z[i]+1) {tot++;break;}
        }
    }
    
    int main() {
        scanf("%s",c);
        n=strlen(c);
        int T;
        tot=0;
        scanf("%d",&T);
        while (T--) {
            memset(pos,inf,sizeof(pos));
            scanf("%s",s);
            len=strlen(s);
            if (len<2) continue;
            for (int i=0;i<n;i++)
                s[i+len+1]=c[i];
            for (int i=0;i<len;i++)
                S[i]=s[len-i-1];
            for (int i=0;i<n;i++)
                S[i+len+1]=c[n-i-1];
            S[len]='$',s[len]='$';
            get_z();
            for (int i=len-1;i>=1;i--)
                pos[i]=min(pos[i+1]-1,pos[i]);
            get_Z();
        }
        printf("%d",tot);
        return 0;
    }