題意：求匹配串在文本中出現(xiàn)次數(shù)，KMP應(yīng)用，理解了就OK了，每次匹配成功就累加次數(shù)，開(kāi)始的時(shí)候超時(shí)，
由于在處理每次成功的時(shí)候讓i=i-len2+1,相當(dāng)于回溯了，后來(lái)一想，本次成功，相當(dāng)于“失敗”，i不動(dòng)，

j需要用哪里來(lái)匹配？當(dāng)然是next{j}!嘛（此處j=len2）。第一次真正敲kmp，完全根據(jù)自己理解敲出來(lái)的總控。

#include<iostream> //用string 220ms，char *，scanf 110ms #include<string> #include<cstdio> #include<cstring> using namespace std; int next[40000]; void get_next(char * s) //next[len]也求得了（有意義）。 {int i=0,j=-1;next[0]=-1;int len=strlen(s);while(i<len){if(j==-1||s[i]==s[j]){i++;j++;if(s[i]==s[j]) //此處只為文本的匹配，可以加快！next[i]=next[j];elsenext[i]=j;}else{j=next[j];}} } int count=0; void kmp(char * tx,char * w) {int i=-1,j=-1; //為了下面++int len2=strlen(w);int len1=strlen(tx);while(i<len1){if(j==-1||tx[i]==w[j]){i++;j++;}else{j=next[j];}if(j==len2) //一次匹配成功，{count++;j=next[j]; //j對(duì)應(yīng)位置。}} } char tx[1000008];char w[10010]; int main() {int ta;cin>>ta;while(ta--){count=0;scanf("%s\n",w);scanf("%s",tx);get_next(w);kmp(tx,w);printf("%d\n",count);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/yezekun/p/3925722.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3461 kmp 应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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