给出两个字符串，寻找一个字符串在另外一个字符串出现的频率。

原来kmp还有一个陷阱，下面注释出了，下标没步进好，就有一定几率出现超时的，也有一定几率出现错误，视具体的串而定。

修改一下就好了，kmp速度是很快的。

#include 
  
   
#include 
   
     const int MAX_TXT = 1000001; const int MAX_WORD = 10001; int gWlen, gTlen; char word[MAX_WORD]; int next[MAX_WORD]; char txt[MAX_TXT]; void getNext() { memset(next, 0, sizeof(int) * gWlen); for (int i = 1, j = 0; i < gWlen; ) { if (word[i] == word[j]) next[i++] = ++j; else if (j > 0) j = next[j-1]; else i++; } } int kmpSearch() { int i = 0, j = 0, ans = 0; for (; gWlen-j <= gTlen-i; ) { if (word[j] == txt[i]) { j++; i++; if (j == gWlen) { ans++; j = next[j-1]; } //else i++; i++放这里会超时，是一定几率会出现超时，注意了！ } else if (j > 0) j = next[j-1]; else i++; } return ans; } int main() { int T; scanf("%d", &T); getchar(); while (T--) { gets(word); gWlen = strlen(word); gets(txt); gTlen = strlen(txt); getNext(); printf("%d\n", kmpSearch()); } return 0; }