631D Messenger

题目大意

给你串s和t

但是每个串都被表示为多个二元组(x,y)表示字符x连续出现y次

问t在s中出现了多少次

分析

我们先将s和t每个串中二元组合并

即相邻两个二元组如果字符相等则将它们变为一个

特判掉m=1的情况

其余情况我们发现对于相等位置除了t的开头结尾两个二元组

其余二元组一定与和s的对应位置完全一样

我们把t去掉头尾放在前面

然后将s放在后面

求出它们的z函数

之后对于s的每个位置如果它的z[i]大于等于m-2

且它的两端字符和t两端相等且个数不小于

那么这个位置合法

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define int long long

char l[],ls[],lt[];

int c[],cs[],ct[],n,m,z[],ans,N;

inline void get_z(){

    int i,j,k,le=,ri=;

    z[]=N;

    for(i=;i<N;i++){

      if(i<=ri)z[i]=min(ri-i+,z[i-le]);

      while(z[i]+i<N&&l[z[i]]==l[z[i]+i]&&c[z[i]]==c[z[i]+i])z[i]++;

      if(z[i]+i->ri)ri=z[i]+i-,le=i;

    }

}

signed main(){

    int i,j,k;

    scanf("%lld%lld",&n,&m);

    for(i=;i<n;i++)scanf("%lld-%c",&cs[i],&ls[i]);

    N=;

    for(i=;i<n;i++)

      if(ls[i]==ls[i-])cs[N]+=cs[i];

        else ls[++N]=ls[i],cs[N]=cs[i];

    n=N+;

    for(i=;i<m;i++)scanf("%lld-%c",&ct[i],&lt[i]);

    N=;

    for(i=;i<m;i++)

      if(lt[i]==lt[i-])ct[N]+=ct[i];

        else lt[++N]=lt[i],ct[N]=ct[i];

    m=N+;

    if(m==){

      for(i=;i<n;i++)

        if(ls[i]==lt[]&&cs[i]>=ct[])ans+=cs[i]-ct[]+;

      printf("%lld\n",ans);

      return ;

    }

    N=n+m-;

    for(i=;i<m-;i++)l[i-]=lt[i],c[i-]=ct[i];

    for(i=;i<n;i++)l[m-+i]=ls[i],c[m-+i]=cs[i];

    get_z();

    for(i=m-;i<N-m+;i++)

      if(z[i]>=m-&&l[i-]==lt[]&&l[i+m-]==lt[m-]&&c[i-]>=ct[]&&c[i+m-]>=ct[m-])ans++;

    printf("%lld\n",ans);

    return ;

}