Codeforces 631D Messenger（Z-Box or kmp）

你的名字 2021-10-18 09:34 236阅读 0赞

## 题意：给出两个分别为n,m项的字符串，求第二个字符串在第一个中出现几次，字符串按照(li,ci)的形式给出。(如2-a 2-b 1-c 表示aabbc)，n，m<=2e5 l<=1e6。 ##

## 分析：字符串总长度过长，直接匹配比较困难，可以把一个字符串（li,ci）看成一个字母。容易发现，去掉头尾两个二元组的话，中间那些部分必须完全相等才能匹配。采用如下方式构造新串：将文本串（大串）接在去掉头尾两个二元组的模式串上，获取它的z数组。 然后我们就可以先找到能够匹配中间部分的位置，此时我们再单独比较头尾是否可行即可。 这种方法需要特判1，因为去掉头尾是无法看出长度为1的串的。参考[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 MAXN=1e6;
    int n,m,z[2*MAXN];
    ll t1[MAXN],t2[MAXN],t[2*MAXN],ans;
    char s1[MAXN],s2[MAXN],s[2*MAXN];
    
    void get_z() {
        int N=n+m-1;
        int l=0,r=0;
        for (int i=1;i<N;i++) {
            if (i>r) {
                l=i,r=i;
                while (r<N && t[r]==t[r-l] && 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 && t[r]==t[r-l] && s[r]==s[r-l]) r++;
                    z[i]=r-l,r--;
                }
            }
        }
    }
    
    int main(){
        char tmp[5],last='$';
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) {
            int x;
            scanf("%d",&t1[i]);
            scanf("%s",tmp);
            if (tmp[1]==last) i--,n--,t1[i]+=t1[i+1];
            s1[i]=tmp[1];
            last=tmp[1];
        }
        last='$';
        for (int i=1;i<=m;i++) {
            scanf("%d",&t2[i]);
            scanf("%s",tmp);
            if (tmp[1]==last) i--,m--,t2[i]+=t2[i+1];
            s2[i]=tmp[1];
            last=tmp[1];
        }
        if (m==1) {
            for (int i=1;i<=n;i++) {
                if (s1[i]!=s2[1]) continue;
                if (t1[i]<t2[1]) continue;
                ans+=(t1[i]-t2[1]+1);
            }
            printf("%lld",ans);
            return 0;
        }
        for (int i=2;i<m;i++)
            s[i-2]=s2[i],t[i-2]=t2[i];
        for (int i=1;i<=n;i++)
            s[i+m-2]=s1[i],t[i+m-2]=t1[i];
        get_z();
        for (int i=m-1;i<=m+n-2;i++) {
            if (z[i]!=m-2) continue;
            if (s[i-1]!=s2[1]) continue;
            if (s[i-2+m]!=s2[m]) continue;
            if (t[i-1]<t2[1]) continue;
            if (t[i-2+m]<t2[m]) continue;
            ans++;
        }
        printf("%lld",ans);
        return 0;
    }

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