有些類似noi2014的動(dòng)物園，也是對(duì)于KMP算法的一個(gè)應(yīng)用，思想就是枚舉前綴然后預(yù)先留出k的位置，對(duì)于自身KMP，當(dāng)next數(shù)組>k時(shí)就計(jì)入答案
#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)注
