POJ_3461

    今天开始学KMP啦，从gestapolur那里听说到Matrix67写的KMP通俗易懂，于是便去那里学了。

#include
     
       #include
      
        #define MAXW 10010 #define MAXT 1000010 int N, P[MAXW]; char word[MAXW], txt[MAXT]; void prepare() {
   int i, j;     P[1] = j = 0; for(i = 2; word[i]; i ++)     {
   while(j && word[j + 1] != word[i])                 j = P[j]; if(word[j + 1] == word[i])             ++ j;         P[i] = j;     } } void solve() {
   int i, j, k, len, cnt = 0;     scanf("%s%s", word + 1, txt + 1);     prepare();     j = 0;     len = strlen(word + 1); for(i = 1; txt[i]; i ++)     {
   while(j && word[j + 1] != txt[i])             j = P[j]; if(word[j + 1] == txt[i])             ++ j; if(j == len)         {
               ++ cnt;             j = P[j];         }     }     printf("%d\n", cnt); } int main() {
   int i; while(scanf("%d", &N) == 1)     {
   for(i = 0; i < N; i ++)             solve();     } return 0; }