POJ.1598 Excuses, Excuses!

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

2.Idea
KMP string matching

3.Source

 int nextarray[1000006];  
 void getnext(string s)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < s.size())  
      {  
           if (j == -1 || s[j] == s[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 int kmp(string &a, string &b)  
 {  
      int i = 0, j = 0, ans = 0;  
      while (i < a.size())  
      {  
           if (j == -1 || a[i] == b[j])  
                ++i, ++j;  
           else  
                j = nextarray[j];  
           if (j == b.size())  
                ++ans, j = nextarray[j];  
      }  
      return ans;  
 }  
 int k, e;  
 string kw[100], es[100];  
 int score[100];  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d%d\n", &k, &e) != EOF) {  
           for (int i = 0; i < k; i++) {  
                cin >> kw[i];  
           }  
           for (int i = 0; i < e; i++) {  
                getline(cin, es[i]);  
                transform(es[i].begin(), es[i].end(), es[i].begin(), ::tolower);  
           }  
           memset(score, 0, sizeof score);  
           int mx = -1;  
           for (int i = 0; i < e; i++) {  
                for (int j = 0; j < k; j++) {  
                     getnext(kw[j]);  
                     score[i] += kmp(es[i], kw[j]);  
                }  
                mx = max(mx, score[i]);  
           }  
           cout << "Excuse Set #" << t++ << endl;  
           for (int i = 0; i < e; i++) {  
                if (score[i] == mx) {  
                     cout << es[i] << endl;  
                }  
           }  
           cout << endl;  
      }  
      return 0;  
 }