POJ.3461 Oulipo

1.Problem
http://poj.org/problem?id=3461

2.Idea
KMP method for string matching

3.Source

 const int maxw = 10000 + 10;   
 const int maxt = 1000000 + 10;   
 //KMP Method  
 int match(char w[], char s[], int next[])  
 {   
      int cnt = 0;  
      int slen = strlen(s);  
      int wlen = strlen(w);  
      int p = 0, cur = 0;  
      while (cur < slen) {   
           if (s[cur] == w[p]) {   
                ++cur;  
                ++p;  
           }  
           else if (p >= 0) {   
                p = next[p];  
           }  
           else {  
                ++cur;  
                p = 0;  
           }  
           if (p == wlen) {   
                ++cnt;  
                p = next[p];  
           }  
      }  
      return cnt;  
 }  
 int main(void)  
 {  
      int loop;  
      scanf("%d", &loop);  
      while (loop--) {  
           char w[maxw], t[maxt];  
           scanf("%s%s", w, t);   
           int suffix[maxw]; // prefix function for word w  
           suffix[0] = -1;  
           suffix[1] = 0;  
           int p = 0;  
           for (int cur = 2; cur <= strlen(w); cur++) {  
                while (p >= 0 && w[p] != w[cur - 1])  
                     p = suffix[p];  
                suffix[cur] = ++p;  
           }  
           printf("%d\n", match(w, t, suffix));   
      }  
      return 0;  
 }