給出兩個字符串,尋找一個字符串在另外一個字符串出現的頻率。
原來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; }