传送门

题意：

给出两个分别为n,m项的字符串

求第二个字符串在第一个中出现几次

字符串按照 (li,ci) ( l i , c i ) 的形式给出

(如2-a 2-b 1-c 表示aabbc)

n,m<=2e5 l<=1e6 n , m <= 2 e 5   l <= 1 e 6

Solution:

直接匹配比较困难

观察发现去掉模式串的首尾两端 中间的串和文本串是完全匹配的，对于完全匹配问题，我们使用双关键字KMP/双关键词x-box即可

最后对于每个匹配位置判断一下头尾即可

注意需要合并连续的相等的c，特判m=1

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mod=1315326179;
int z[400010],n,m,r,l,p,x;
long long b[200010],a[200010],num[400010];
char s1[200010],s2[200010],S[400010];
int wei;
int ans=0;
char s[5];
char pre=0;
int fast_pow(int a,int x)
{
    int ans=1;
    for (;x;x>>=1,a=1ll*a*a%mod) 
        if (x&1) ans=1ll*ans*a%mod;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        scanf("%s",s);
        //cout<<s<<" "<<x<<endl;
        if (s[1]==pre) i--,n--,a[i]+=x;
        else a[i]=x,s2[i]=s[1];
        pre=s[1];
    }
    pre='1';
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        scanf("%s",s);
        if (s[1]==pre) i--,m--,b[i]+=x;
        else b[i]=x,s1[i]=s[1];
        pre=s[1];
    }
    if (m==1)
    {
        long long ans=0;
        for (int i=1;i<=n;i++)
            if (s2[i]==s1[1]&&a[i]>=b[1]) ans+=a[i]-b[1]+1;
        printf("%lld",ans);
        return 0;
    }
    for (int i=2;i<m;i++)
        S[i-2]=s1[i],num[i-2]=b[i];
    for (int i=1;i<=n;i++)
        S[m+i-2]=s2[i],num[i+m-2]=a[i];
// for (int i=0;i<=m+n-2;i++)
// {
   
// printf("%c %d\n",S[i],num[i]);
// }
    for (int i=1;i<=m+n-2;i++)
    {
        if (i>r)
        {
            int t=i,bg=0;
            while (S[t]==S[bg]&&num[t]==num[bg])
                t++,bg++;
            z[i]=bg;
            r=t-1;
            l=i;
        }
        else
        {
            if (z[i-l]<r-i+1) z[i]=z[i-l];
            else
            {
                int t=r+1,bg=r-i+1;
                while (S[t]==S[bg]&&num[t]==num[bg])
                    t++,bg++;
                z[i]=bg;
                r=t-1;
                l=i;
            }
        }
    }
    for (int i=m-1;i<=m+n-2;i++)
        if (z[i]==m-2)
            if (S[i-1]==s1[1]&&num[i-1]>=b[1]&&S[i+m-2]==s1[m]&&num[i+m-2]>=b[m]) ans++;
    printf("%d",ans);
}