這里KMP有兩種寫法，一開(kāi)始我是照著zyf2000的模板學(xué)的 跟她完全一樣所以我直接先粘過(guò)來(lái)
#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int max_W=10005;const int max_s=1000005;char W[max_W],s[max_s];int T[max_W];int t,len_W,len_s,ans;inline void calc_T(){ T[0]=-1; int j; for (int i=0;i<len_W;++i){ j=T[i]; while (j!=-1&&W[j]!=W[i]) j=T[j]; T[i+1]=++j; }}inline void calc_ans(){ int j=0; for (int i=0;i<len_s;++i){ while (j!=-1&&W[j]!=s[i]) j=T[j]; j++; if (j==len_W){ ans++; j=T[j]; } }}int main(){ scanf("%d/n",&t); while (t--){ gets(W); gets(s); len_W=strlen(W); len_s=strlen(s); memset(T,0,sizeof(T)); calc_T(); ans=0; calc_ans(); 一開(kāi)始我是這么寫的，慢慢發(fā)現(xiàn)這樣寫實(shí)際對(duì)于有些題目并不適用，然后改成了另外一種寫法，其實(shí)就是字符串從1開(kāi)始計(jì)數(shù)，對(duì)于有些題比較方便。好像沒(méi)有現(xiàn)成的模板也懶得再敲一遍了貼一下bzoj3620吧，事實(shí)上這道題的KMP體現(xiàn)的并不形象.noi2014的動(dòng)物園比較形象，但是當(dāng)時(shí)我還是照著第一種寫的所以WA了好幾次，改成第二種之后就不會(huì)出現(xiàn)我的錯(cuò)法了。#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;#define N 15005char s[N];int f[N];int k,l,ans,lim;int main(){ scanf("%s%d",s+1,&k); l=strlen(s+1);lim=l-k*2; for (int p=0;p<lim;p++)//枚舉左端點(diǎn)，對(duì)每一個(gè)左端點(diǎn)做KMP { for (int j=0,i=2;i+p<l;i++)//處理next（f）數(shù)組 { while (j&&s[j+p+1]!=s[i+p])j=f[j]; if (s[i+p]==s[j+p+1])j++;f[i]=j; } for (int j=0,i=k+1;i+p<=l;i++)//類似noi2014的動(dòng)物園 { while (j&&s[i+p]!=s[j+p+1])j=f[j]; if (s[i+p]==s[j+p+1])j++; while ((j<<1)>=i)j=f[j];if (j>=k)ans++;//當(dāng)前綴與后綴都>=k即j>=k時(shí)并且<=i>>1時(shí)計(jì)入答案 } } cout<<ans; return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
