题意：

给定由字符串块（字符及连续出现的个数）组成的字符串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\n",KMP_count());

   }

   return 0;

}

思考思考思考~相信自己一定可以做出来的~~

吐槽：为啥么越来越觉得D比C 好做呢~