题意：
给定由字符串块（字符及连续出现的个数）组成的字符串t,s，求t串中有多少个s。
分析：
KMP
这题唯一需要思考的地方就是如何处理字符串块。第一想到是把他们都展开然后进行KMP，可是展开后实在太长，所以必须按块进行处理，就要把所有相邻的相同的块进行合并成一个大块。
注意模式串开头和结尾处与t中对应的块不需要严格相等，只要字符相同并且t中个数不小于模式串中的个数~~所以只需将模式串去掉开头和结尾进行匹配，最后再判断一下就好啦~
既然要去掉开头结尾，就要保证原模式串s的长度大于2，所以长度为1和2的情况都需要特殊考虑一下~
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 200005;
typedef long long ll;
typedef pair<char, ll> pii;
#define fi first
#define se second
pii s[maxn], t[maxn], ms[maxn];
int m, n, mm;
int next[maxn];
void KMP_pre()
{
int j = next[0] = -1;
int i = 0;
while(i < mm){
while(j != -1 && ms[i] != ms[j]) j = next[j];
next[++i] = ++j;
}
}
ll KMP_count()
{
int i = 0, j = 0;
ll ans = 0;
while(i < n){
while(j != -1 && t[i]!= ms[j]) j = next[j];
i++, j++;
if(j >= mm){
if(i < n && t[i - mm - 1].fi == s[0].fi && t[i - mm - 1].se >= s[0].se
&& t[i].fi == s[m - 1].fi && t[i].se >= s[m - 1].se){
ans++;
}
j = next[j];
}
}
return ans;
}
int main (void)
{
int N, M;
scanf("%d%d", &N, &M);
m = n = mm = 0;
ll tl;
char tc;
for(int i = 0; i < N; i++){
scanf("%I64d-%c", &tl, &tc);
if(i == 0){
t[n++] = pii(tc, tl);
}else{
if(tc == t[n - 1].fi)
t[n - 1].se += tl;
else
t[n++] = pii(tc, tl);
}
}
//for(int i = 0; i < n; i++) cout<<t[i].fi<<' '<<t[i].se<<endl;
for(int i = 0; i < M; i++){
scanf("%I64d-%c", &tl, &tc);
if(i == 0){
s[m++] = pii(tc, tl);
}else{
if(tc == s[m - 1].fi)
s[m - 1].se += tl;
else
s[m++] = pii(tc, tl);
}
}
// for(int i = 0; i < m; i++) cout<<s[i].fi<<' '<<s[i].se<<endl;
if(m == 1){
ll ans = 0;
for(int i = 0; i < n; i++){
if(t[i].fi== s[0].fi && t[i].se >= s[0].se)
ans += t[i].se - s[0].se + 1;
}
cout<<ans<<endl;
}else if(m == 2){
ll ans = 0;
for(int i = 0; i < n - 1; i++){
if(t[i].fi == s[0].fi && t[i].se >= s[0].se
&& t[i +1].fi == s[1].fi && t[i + 1].se >= s[1].se)
ans++;
}
cout<<ans<<endl;
}else{
mm = 0;
for(int i = 1; i < m - 1; i++)
ms[mm++] = s[i];
KMP_pre();
printf("%I64d
",KMP_count());
}
return 0;
}思考思考思考~相信自己一定可以做出来的~~
吐槽：为啥么越来越觉得D比C 好做呢~