题目链接 http://codeforces.com/contest/631/problem/D， 大体思路是将头尾去掉， 然后匹配中间， 匹配好后在比较两边， 代码如下：
#include <bits/stdc++.h> using namespace std; typedef pair<char, long long> pcl; vector<pcl> s, t; int n, m; int next[200000+100]; int tpnum; char str[10]; void getnext(){ int i=1, j=0; next[1] = 0; while(i<t.size()-1){ if(j==0 || t[i]==t[j]){ ++i; ++j; next[i] = j; } else j = next[j]; } } long long KMP(){ long long res = 0; int i=0, j=1; while(i<s.size()){ if(j==0 || s[i]==t[j]) i++, j++; else j = next[j]; if(j==t.size()-1){ if(s[i].first==t[j].first&&s[i].second>=t[j].second&& s[i-t.size()+1].first==t[0].first && s[i-t.size()+1].second>=t[0].second) res++; j = next[j]; } } return res; } int main(){ // freopen("1", "r", stdin); scanf("%d%d", &n, &m); for(int i=0; i<n; i++){ scanf("%d-%s", &tpnum, str); int sz = s.size(); if(sz==0 || s[sz-1].first!=str[0]){ s.push_back((pcl){str[0], tpnum}); } else s[sz-1].second += tpnum; } for(int i=0; i<m; i++){ scanf("%d-%s", &tpnum, str); int sz = t.size(); if(sz==0 || t[sz-1].first!=str[0]){ t.push_back((pcl){str[0], tpnum}); } else t[sz-1].second += tpnum; } // for(int i=0; i<s.size(); i++) { // printf("%c %lld ", s[i].first, s[i].second); // } // printf(" "); // for(int i=0; i<t.size(); i++) { // printf("%c %lld ", t[i].first, t[i].second); // } // printf(" "); long long res = 0; if(t.size() == 1) { for(int i=0; i<s.size(); i++) if(t[0].first==s[i].first && s[i].second>=t[0].second) res += s[i].second-t[0].second+1; printf("%I64d ", res); return 0; } if(t.size() == 2){ for(int i=0; i<s.size()-1; i++) if(t[0].first==s[i].first&&t[0].second<=s[i].second&& t[1].first==s[i+1].first&&t[1].second<=s[i+1].second) res++; printf("%I64d ", res); return 0; } getnext(); printf("%I64d ", KMP()); return 0; }