題意

“Madoka,不要相信 QB！”伴隨著 Homura 的失望地喊叫,Madoka 與 QB 簽訂了契約.
這是 Modoka 的一個噩夢,也同時是上個輪回中所發(fā)生的事.為了使這一次 Madoka 不再與 QB簽訂契約,Homura 決定在剛到學校的第一天就解決 QB.然而,QB 也是有許多替身的(但在第八話中的劇情顯示它也有可能是無限重生的),不過,意志堅定的 Homura 是不會放棄的——她決定
消滅所有可能是 QB 的東西.現(xiàn)在，她已感受到附近的狀態(tài),并且把它轉(zhuǎn)化為一個長度為 n 的字符串交給了學 OI 的你.
現(xiàn)在你從她的話中知道 , 所有形似于 A+B+A 的字串都是 QB 或它的替身 , 且len(A)>=k,len(B)>=1 （位置不同其他性質(zhì)相同的子串算不同子串,位置相同但拆分不同的子串算同一子串）,然后你必須盡快告訴 Homura 這個答案——QB 以及它的替身的數(shù)量.
n<=15000 , k<=100，且字符集為所有小寫字母

分析

一開始就往sa和sam上面去想了，發(fā)現(xiàn)還是不會做，后來看了一波題解，發(fā)現(xiàn)只要n2就能過。

對于一個區(qū)間[l,r]，如果有一個w滿足長為w的前綴等于長為w的后綴且w>=k,w<=(r-l)/2那么該區(qū)間即為合法區(qū)間。
那么我們可以枚舉左端點l，然后求出其next數(shù)組，用一個輔助數(shù)組f[i]表示i不停地往next走，能走到的最小的且不小于k的長度是多少，然后掃一遍統(tǒng)計右端點貢獻即可。

代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 15005 using namespace std;int k,f[N],n,next[N]; char s[N];void get_next(int x) {next[x]=x-1;next[x-1]=x-2;int i=x+1,j=x-1;while (i<=n)if (s[j+1]==s[i]||j==x-2){j++;next[i]=j;i++;}else j=next[j]; }int main() {scanf("%s",s+1);n=strlen(s+1);scanf("%d",&k);int ans=0;for (int i=1;i<=n-k*2;i++){get_next(i);for (int j=i+1;j<=n;j++){f[j]=0;if (next[j]-i+1>=k) f[j]=next[j]-i+1;if (f[next[j]]>=k) f[j]=min(f[j],f[next[j]]);if (f[j]>=k&&f[j]<=(j-i)/2) ans++;}}printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的bzoj 3620: 似乎在梦中见过的样子 kmp算法+暴力的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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