Codeforces 535D Tavas and Malekas（Z-Box or kmp）

小鱼儿 2021-10-18 09:30 214阅读 0赞

## 题意：给你一个模式串和原串的长度，并且告诉你模式串再原串中出现的位置，求原串有几种可能。 ##

## 分析：预处理出z数组。对于有限制的每一个位置，先判断答案是否可行。有两种可能：这个串和前一个串有重合或没有重合。没有重合我们就默认他可以放在这里。如果有重合怎么办呢？前面的z数组就可以派上用场了。计算出重合的长度吗，如果这段长度的后缀和前缀是完全匹配的，那么就可以，否则就是不合法的。如何找出没有限制的位置来计算总数，采用差分的方法，区间打上标记表示被占用过，最后统计数量（差分前缀和为0）。参考[https://blog.csdn.net/szh\_0808/article/details/79257961][https_blog.csdn.net_szh_0808_article_details_79257961]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1000010;
    const int mod=1e9+7;
    char s[N];
    int z[N],n,m,pos[N],a[N],len;
    
    void get_z() {
        int l=0,r=0;
        for (int i=1;i<len;i++) {
            if (i>r) {
                l=i,r=i;
                while (r<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<len && s[r]==s[r-l]) r++;
                    z[i]=r-l,r--;
                }
            }
        }
    }
    
    bool ck(int x,int y) {
        if (x+n<=y) return true;
        return z[y-x]>=x+len-y;
    }
    
    int qp(int a,int b) {
        ll ans=1,x=a;
        while (b) {
            if (b&1) ans*=x;
            b/=2;
            x*=x;
            ans%=mod,x%=mod;
        }
        return ans;
    }
    
    int main() {
        scanf("%d%d",&n,&m);
        if (!m) {
            printf("%d",qp(26,n));
            return 0;
        }
        scanf("%s",s);
        len=strlen(s);
        get_z();
        for (int i=1;i<=m;i++) {
            scanf("%d",&pos[i]);
            pos[i]--;
        }
        int tot=0;
        for (int i=1;i<m;i++) {
            if (ck(pos[i],pos[i+1]))
                a[pos[i]]++,a[pos[i]+len]--;
            else {
                printf("0");
                return 0;
            }
        }
        a[pos[m]]++,a[pos[m]+len]--;
        for (int i=0;i<n;i++)
            a[i]+=a[i-1];
        for (int i=0;i<n;i++)
            if (!a[i]) tot++;
        printf("%d",qp(26,tot));
        return 0;
    }

[https_blog.csdn.net_szh_0808_article_details_79257961]: https://blog.csdn.net/szh_0808/article/details/79257961