【CF#613D】Messenger

  • 本文为博主原创,未经许可不得转载

题目大意:

给出两个字符串长度为n,m的S,T的压缩形式(x,ch),询问一个串在另一个串里的出现次数


分析:

忽略匹配串的开头和结尾,做kmp,然后O(1)判断是否合法

注意特判m=1和m=2的情况

代码实现细节繁多,调了一个下午

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 600100
using namespace std;
typedef long long ll;
ll n,m,ans,cnt1,cnt2,next[MAXN],PA[MAXN],PB[MAXN],a[MAXN],b[MAXN];
char A[MAXN],B[MAXN];
void solve(){
if(m==1){
for(ll i=1;i<=n;++i)if(A[i]==B[1]&&PA[i]>=PB[1])ans+=PA[i]-PB[1]+1;
printf("%lld\n",ans);
return;
}
else{
for(ll i=1;i<n;++i)if(A[i]==B[1]&&PA[i]>=PB[1]&&A[i+1]==B[2]&&PA[i+1]>=PB[2])++ans;
printf("%lld\n",ans);
return;
}
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
scanf("%d%d",&n,&m); ll tot=0;
for(ll i=1;i<=n;++i) scanf("%d-%c",&PA[i],&A[i]);
for(ll i=1;i<=m;++i) scanf("%d-%c",&PB[i],&B[i]);
for(ll i=1;i<=n;++i){
ll t=i; PA[++tot]=PA[i]; A[tot]=A[i];
while(A[i]==A[t+1]&&t<n) PA[tot]+=PA[t+1],++t;
i=t;
}n=tot; tot=0;
for(ll i=1;i<=m;++i){
ll t=i; PB[++tot]=PB[i]; B[tot]=B[i];
while(B[i]==B[t+1]&&t<m) PB[tot]+=PB[t+1],++t;
i=t;
}m=tot; tot=0;
if(m<=2) {solve(); return 0;}
for(ll i=1;i<=n;++i)a[++cnt1]=PA[i]+300,a[++cnt1]=(ll)A[i];
for(ll i=2;i<m;++i) b[++cnt2]=PB[i]+300,b[++cnt2]=(ll)B[i];
for(ll i=2,j=0;i<=cnt2;++i){
while(j&&b[j+1]!=b[i]) j=next[j];
if(b[j+1]==b[i]) ++j; next[i]=j;
}
for(ll i=1,j=0;i<=cnt1;++i){
while(j&&b[j+1]!=a[i]) j=next[j];
if(b[j+1]==a[i]) ++j;
if(j==cnt2){
ll temp=i-cnt2+1;
if(a[temp-1]==B[1]&&a[temp-2]-300>=PB[1]&&a[i+2]==B[m]&&a[i+1]-300>=PB[m]) ++ans;
}
}
printf("%lld\n",ans);
return 0;
}
文章目录
,