鑒于兩個(gè)字符串，尋找一個(gè)字符串的頻率，另一個(gè)字符串出現(xiàn)。

原版的kmp另一個(gè)陷阱。以下凝視了，標(biāo)不是踩著好，有加班一定幾率，也有機(jī)會(huì)錯(cuò)誤，根據(jù)不同的字符串可以是詳細(xì)。

變化看起來(lái)像一個(gè)，kmp速度是非常快的。

#include <stdio.h> #include <string.h>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++放這里會(huì)超時(shí)，是一定幾率會(huì)出現(xiàn)超時(shí)。注意了！}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; }

版權(quán)聲明：筆者靖心臟，景空間地址：http://blog.csdn.net/kenden23/。只有經(jīng)過(guò)作者同意轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的HDU 1618 Oulipo KMP解决问题的方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。