题目大意
给你串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],<[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 ;
}