首先想到kmp， 和普通的不一样的是，中间部分严格相等， 头和尾的字符相等但是数量可以不相等。 所以应该把子串的头和尾先去掉，然后对剩下的部分进行kmp。
子串长度为1或2要特别讨论。
不要忘记一开始先把相邻的相同的部分合并掉。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 2e5+;
pair <ll, char> a[maxn], b[maxn];
#define next nextt
int n, m, next[maxn];
void init_kmp() {
int i = , j = -;
next[] = -;
while(i<m) {
if(j == - || b[i] == b[j]) {
++i, ++j;
next[i] = j;
} else {
j = next[j];
}
}
}
int main()
{
int x;
char ch;
cin>>n>>m;
for(int i = ; i<n; i++) {
scanf("%I64d-%c", &x, &ch);
a[i] = mk(x, ch);
}
for(int i = ; i<m; i++) {
scanf("%I64d-%c", &x, &ch);
b[i] = mk(x, ch);
}
int cnt = ;
for(int i = ; i<n-; i++) {
if(a[i].se == a[i+].se) {
a[cnt].fi += a[i+].fi;
continue;
}
a[++cnt] = a[i+];
}
n = cnt+;
cnt = ;
for(int i = ; i<m-; i++) {
if(b[i].se == b[i+].se) {
b[cnt].fi += b[i+].fi;
continue;
}
b[++cnt] = b[i+];
}
m = cnt+;
ll ans = ;
if(m == ) {
for(int i = ; i<n; i++) {
if(a[i].se == b[].se&&a[i].fi>=b[].fi) {
ans += (a[i].fi-b[].fi+);
}
}
cout<<ans<<endl;
return ;
}
if(m == ) {
for(int i = ; i<n-; i++) {
if(a[i].se == b[].se && a[i+].se == b[].se && a[i].fi>=b[].fi&&a[i+].fi>=b[].fi) {
ans ++;
}
}
cout<<ans<<endl;
return ;
}
pair <ll, char> s, e;
s = b[], e = b[m-];
cnt = ;
for(int i = ; i<m-; i++) {
b[cnt++] = b[i]; //去掉头尾
}
m -= ;
init_kmp();
int i = , j = ;
while(i<n-) {
if(j == - || a[i] == b[j]) {
i++, j++;
} else {
j = next[j];
}
if(j == m) {
if(s.se == a[i-j-].se && s.fi<=a[i-j-].fi
&& a[i].se == e.se && a[i].fi>=e.fi) {
ans++;
}
j = next[j];
}
}
cout<<ans<<endl;
return ;
}