CSP 前填坑，但是這玩意好簡單，感覺學了自動機之后這一類串串題都非常容易理解了。

Manacher

用途和 KMP 比較像，不怎么能在上面 dp，但是有可能會有其思想的延伸應用。

天依寶寶可愛！

洛谷 P3805

板子。

下面「回文串 \(i\)」及類似的東西的意思就是「以 \(i\) 為中心的回文串」。

首先為了統一奇數回文和偶數回文，需要把字符串搞成 #a#b#c#d# 的樣子。

具體思路就是維護一個 \(p_i\) 表示以 \(i\) 為中點的最長回文串的一半長度。

例如對于串 #a#b#a#，\(p_i = 4\)。

然后再維護一個 \(j\) 和一個 \(r\)，表示在已經做完的位置（即 \(1 \sim i-1\)）中回文串能延伸到的最靠右位置為 \(r\)，能延伸到 \(r\) 的這個串的中點為 \(j\)，注意我們并不關心有多個 \(j\) 的情況，隨便一個即可。

例如對于串 #x#c#b#c#a#c#b#c#y#，假設當前做到了最后面那個 b，此時前面那個 a 能延伸到的最大位置 \(r=17\) 也就是 y 前面那個 # 的位置，\(j=10\) 也就是 a 的位置。

那么在算 \(p_i\) 的時候，就可以根據 \(j,r\) 來搞事情了。

1. 當 \(i<r\) 時，\(i\) 是可以完全被 \(j\) 這個回文串覆蓋的，于是令 \(i’\) 為 \(i\) 關于 \(j\) 的對稱點，那么在回文串 \(j\) 的范圍內，\(i’\) 回文的部分對應到 \(i\) 上也一定回文，即 \(p_i \ge \min(p_{i'} , r-i)\)，根據回文串的性質顯然。于是先令 \(p_i \gets \min(p_{i'} , r-i)\)。

   但是這還不夠，因為回文串 \(i\) 不一定只有這么短，還有可能延伸到回文串 \(j\) 的外面，所以還需要往外擴展，可以發(fā)現此時就沒有什么能利用的東西了，所以直接暴力擴展即可。

2. 當 \(i > r\) 時，直接暴力擴展就可以。

3. 哦你說 \(i = r\)，隨便丟到哪個情況里都是一樣的。

復雜度是 \(O(n)\) 的，因為只要出現了暴力擴展，那么一定是因為需要擴展的范圍超過了 \(r\) 導致的，所以就一定會更新 \(r\)。那么顯然 \(O(n)\)。

最后放個代碼：

{s="$#"; char c; while(read(c),!fast_io::isEOF) s+=c,s+='#';}
n=s.size()-1;

int r=0,j=0,ans=0;
rep(i,1,n)
{
    p[i]=r>i?min(p[(j<<1)-i],(signed)(r-i)):1; // 冒號前是情況 1，冒號后是情況 2
    while(s[i-p[i]]==s[i+p[i]]) ++p[i]; // 暴力往外擴展
    i+p[i]>=r && (r=i+p[i],j=i); // 更新 j,r
    chmax(ans,p[i]-1); // 更新答案
}

write(ans);

submission

天依寶寶可愛！

洛谷 P4555

思維難度：\(\color{#F39C11} 橙\) *1100

顯然是先跑一遍 Manacher，然后求一個 \(l_i\) 表示以 \(i\) 為左端點的回文串的最右端點，\(r_i\) 同理，然后取 \(\max _{i} \{ l_i - r_i + 1 \}\) 就是答案。

這個直接對每個 \(i \pm p_i\) chmax/min 一遍不就好了？但是發(fā)現不過樣例，因為這樣只考慮了最長回文串，并沒有考慮較短的回文串會和另一個更長的回文串組合的情況。

于是要 \(\forall j \le p_i\)，都更新一遍 \(i \pm j\)，發(fā)現可以上線段樹，于是做完了。

但是作為一名數據結構不愛好者，我們發(fā)現這玩意可以直接做一遍前綴 max（后綴 min）來求，于是便在 \(O(n)\) 的復雜度內做完了。

注意考慮回文串不能是空串的情況，也就是 # 不能單獨作為一個回文串，也就是必須滿足 \(l_i > i \land r_i < i\)。

submission

天依寶寶可愛！

CF1326D2

思維難度：\(\color{#FE4C61} 紅\) *900

把前后綴能構成回文的扣出來，剩下的部分選一個最長的回文前綴或后綴即可。

submission

天依寶寶可愛！