# 10047. 「一本通 2.2 練習 3」似乎在夢中見過的樣子

【題目描述】

「Madoka，不要相信 QB！」伴隨著 Homura 的失望地喊叫，Madoka 與 QB 簽訂了契約。

這是 Modoka 的一個噩夢，也同時是上個輪回中所發生的事。為了使這一次 Madoka 不再與 QB 簽訂契約，Homura 決定在剛到學校的第一天就解決 QB。然而，QB 也是有許多替身的（但在第八話中的劇情顯示它也有可能是無限重生的），不過，意志堅定的 Homura 是不會放棄的——她決定消滅所有可能是 QB 的東西。現在，她已感受到附近的狀態，并且把它轉化為一個長度為 nnn 的字符串交給了學 OI 的你。

現在你從她的話中知道，所有形似于 $A+B+A$ 的字串都是 QB 或它的替身，且 $|A|\ge k,|B|\ge 1$（位置不同其他性質相同的子串算不同子串，位置相同但拆分不同的子串算同一子串），然后你必須盡快告訴 Homura 這個答案——QB 以及它的替身的數量。

【算法】a

基本地：由于 $O(n^2)$ 就行，枚舉子串左端點，計算每個子串的特征向量，對符合要求的累加。
特別地：KMP中計算的特征向量 $nxt[i]$ 表示的是以i為右端點，題目中A串的最小長度，由于題目對A的長度做了限制。于是，我們另開一個數組 $f$，記錄滿足A長度條件的最小長度 j，若 j 同時滿足 $2*j<i$ 則累加。
收獲：nxt數組本質上可以看作父節點表示法表示的一顆樹，我們自根向下延申。要記錄的是中間的滿足條件的點。（之前最大循環節那道題 f 數組記錄的就是根節點的值，不過我沒意識到是棵樹。。）

【代碼】

#include <bits/stdc++.h> #define ll long long using namespace std; int k,n; ll ans; int nxt[20000],f[20000]; char s[20000]; void get_nxt(int x) {nxt[1]=0;for(int i=2,j=0;i<=n-x;i++) {while(j>0&&s[i+x]!=s[j+x+1]) j=nxt[j];if(s[j+x+1]==s[i+x]) j++;nxt[i]=j;if(f[j]) f[i]=f[j];else if(j>=k) f[i]=j;else f[i]=0;if(f[i]&&(f[i]<<1)<i) ans++;} } int main() {scanf("%s%d",s+1,&k);n=strlen(s+1);for(int i=1;i<=n;i++) {get_nxt(i-1);}printf("%lld\n",ans);return 0; }

轉載于:https://www.cnblogs.com/Willendless/p/9614641.html

總結

以上是生活随笔為你收集整理的似乎在梦中见过的样子 (KMP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。