Codeforces 631D Messenger（Z-Box or kmp）-蒲公英云

Codeforces 631D Messenger（Z-Box or kmp）

你的名字 2021-10-18 09:34 290阅读 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。

代码：

#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;
}