肝了不知道多久的串串，終于把這個東西學明白了

先掛上大佬的博客：https://www.cnblogs.com/Parsnip/p/12426971.html

這個東西簡稱我也不知道叫什么，只知道在某些方面真的比較好用

先得知道一系列的前置知識，建議去閱讀論文：金策_字符串算法選講

前置知識是：弱周期定理、字符串Border、Border Series和一個很重要的結論：一個回文串的所有回文后綴可以表示為 O(logn) 段等差數列

然后就可以去做一些奇奇怪怪的優(yōu)化了，比如對于某個前綴 s[ i ] 來說，需要枚舉其所有回文后綴的貢獻，如果暴跳fail樹的話，會被“aaaa....aaa”這種字符串卡成 O( n ) 級別的，而如果套用上面的理論，則可以將所有的回文后綴視為 logn 段等差數列，因為每段等差數列結束的位置以及前一次結束的位置都相同，所以可以一起維護，時間復雜度下降到了 O( logn )

Border?Series最經典的應用就是回文串劃分的 dp，其實現也非常的簡單，只需要在 PAM 中增加一個函數用于代替暴跳fail樹即可

這里用的是葫蘆爺的轉移代碼，相信會PAM的同學肯定不陌生吧，就不多bb了

符號約定：

len[ i ]?表示節(jié)點代表的回文串長度

fail[ i ]?表示節(jié)點的失配指針，即最長的回文后綴，即最大border。

diff[ i ] = len[ i ] ? len[ fail[ i ] ]?，表示一個節(jié)點和他最大border長度的差，即所在的等差數列的公差。

anc[ i ]?表示節(jié)點所在等差數列的首項位置，即從 i 開始往根走，保證 diff 值都相同，最終走到的點。

g[ i ]?維護每個點到鏈頂的信息，維護的范圍是( len[ anc[ i ] ] , len[ i ] ]，公差 d = diff[ i ]。

f[ i ]?表示DP值，即將串?S[ 1 , i ] 進行分割的方案數。

題目的話后續(xù)會慢慢補上的，個人喜好，不喜歡在同一篇博客中寫多個題目

void trans(int i) {for(int j=last;j>1;j=anc[j]){g[j]=f[i-len[anc[j]]-diff[j]];if(diff[j]==diff[fail[j]])g[j]=(g[j]+g[fail[j]])%mod;f[i]=(f[i]+(i%2==0)*g[j])%mod;} }

?

總結

以上是生活随笔為你收集整理的字符串科技：Palindrome Series的全部內容，希望文章能夠幫你解決所遇到的問題。

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