CodeForces 631D Messenger —— （kmp的应用）

　　这题是一个kmp的应用，思路是有，但是代码实现能力太弱，细节考虑不全，敲了很长时间才AC。。

　　题意：字符串用如下的方法表示，例如aaabbbbcc表示为3-a，4-b，2-c。那么问t串在s串中出现了多少次。这题的字符串总长是很长的，如果扩展为原长再kmp内存都不够。那么只能对缩写的状态进行kmp。

　　方法如下：

　　1.如果缩写长度为1，那么用这个在s串中每个进行比对字符和长度即可。

　　2.如果为2，也类似于1。

　　3.如果缩写长度大于3，那么由于头和尾匹配的时候不是需要长度也相等，只要长度小于或者等于即可，那么，先把头尾去掉。将身子进行kmp，每个点相同的条件应当是长度和字符都完全相等。其实这里可以写成pair来比较一个点更方便，但是我是用的两个数组，结果写的很挫。。当身子满足以后，再比较头和尾是否满足即可。

　　这里有个注意点，在输入的时候如果相邻两个字符时相同的，需要合并，不然会出错。比方说3-a，4-a，用2-a去匹配，在3-a和4-a中间其实也可以放一个2-a，所以不合并的话答案就少了1。

　　具体见代码：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <string>
  5 #include <map>
  6 #include <vector>
  7 #include <iostream>
  8 using namespace std;
  9 typedef long long ll;
 10 const int N = 200000+5;
 11 
 12 char s[N],t[N],tt[N];
 13 int lena,lenb;
 14 ll numa[N],numb[N];
 15 int nxt[N];
 16 int f,e;
 17 
 18 void getnxt()
 19 {
 20     nxt[1] = 0;
 21     int j = 0;
 22     for(int i=2;i<=lenb-2;i++)
 23     {
 24         while(j>0 && (tt[j+1]!=tt[i] || numb[i]!=numb[j+1]) ) j=nxt[j];
 25         if(tt[j+1] == tt[i] && numb[i]==numb[j+1]) j++;
 26         nxt[i]=j;
 27     }
 28 }
 29 
 30 ll kmp()
 31 {
 32     ll ans = 0;
 33     int j = 0;
 34     for(int i=2;i<lena;i++)
 35     {
 36         while(j>0 && (tt[j+1]!=s[i] || numa[i]!=numb[j+1]) ) j=nxt[j];
 37         if(tt[j+1]==s[i] && numa[i]==numb[j+1]) j++;
 38         if(j == lenb-2)
 39         {
 40             if(s[i-(lenb-2)]==t[1] && s[i+1]==t[lenb] && numa[i-(lenb-2)]>=f && numa[i+1]>=e) ans++;
 41             j = nxt[j];
 42         }
 43     }
 44     return ans;
 45 }
 46 
 47 int main()
 48 {
 49     int n,m;
 50     lena = lenb = 0;
 51     cin>>n>>m;
 52     for(int i=1;i<=n;i++)
 53     {
 54         ll x;
 55         char c[2];
 56         scanf("%I64d-%s",&x,c);
 57         if(c[0]==s[lena]) numa[lena] += x;
 58         else
 59         {
 60             numa[++lena] = x;
 61             s[lena] = c[0];
 62         }
 63     }
 64 
 65     for(int i=1;i<=m;i++)
 66     {
 67         ll x;
 68         char c[2];
 69         scanf("%I64d-%s",&x,c);
 70         if(c[0]==t[lenb]) numb[lenb] += x;
 71         else
 72         {
 73             numb[++lenb] = x;
 74             t[lenb] = c[0];
 75         }
 76     }
 77 
 78     ll ans = 0;
 79     if(lenb == 1)
 80     {
 81         for(int i=1;i<=lena;i++)
 82         {
 83             if(s[i]==t[1] && numa[i]>=numb[1])
 84             {
 85                 ans += (ll)numa[i]-numb[1]+1;
 86             }
 87         }
 88     }
 89     else if(lenb == 2)
 90     {
 91         for(int i=1;i<lena;i++)
 92         {
 93             if(s[i]==t[1] && s[i+1]==t[2] && numa[i]>=numb[1] && numa[i+1]>=numb[2]) ans ++;
 94         }
 95     }
 96     else
 97     {
 98         strcpy(tt+1,t+2);
 99         tt[lenb] = 0;
100         f = numb[1],e = numb[lenb];
101         for(int i=1;i<lenb;i++) numb[i]=numb[i+1];
102 
103         getnxt();
104         ans = kmp();
105     }
106     printf("%I64d
",ans);
107     return 0;
108 }