【沒有前置知識】

?

---

?

【解決的問題】

大多數(shù)都和回文串有關(guān)

例如：

字符串中長度最長的回文串

?

---

?

【算法學(xué)習(xí)】

manacher優(yōu)秀的地方在于，他能夠在線性時間內(nèi)求出每個字符所對應(yīng)的以其自身為中心的最長回文串長度

（請牢記這個目的）

?

先來講樸素算法：

從1~n，對每個字符都從其自身開始，向兩邊遞推，如果左右兩邊字符相同，范圍+1，長度+2

這樣的復(fù)雜度是n^2的

?

而 manacher 的優(yōu)化方式和 kmp 有所類似，都是利用之前已經(jīng)匹配過和得到過的信息，簡化當(dāng)前的運算

?

回文串有兩種，一種是奇數(shù)長度一種是偶數(shù)長度，顯然他們是需要被區(qū)別對待的

但是在理解了manacher的本質(zhì)之后，我們只需要做微小改動就能夠同時解決這兩個問題?

?

首先引入 l 和 r ，代表當(dāng)前已經(jīng)找到的回文串中，右端點最右的回文串的左右端點，初始為 0 和 1

設(shè)數(shù)組d為我們所需要求取的數(shù)組，即每個字符所對應(yīng)的以其自身為中心的最長回文串長度

假設(shè)我們現(xiàn)在要求d [ i ] 的值，而 d [ i ] 之前的值已經(jīng)求出來了

當(dāng)我們現(xiàn)在所求的 i < r 時，即現(xiàn)在這個字符是在一個回文串中的時候

我們就可以利用這個信息，來處理他

求在（l，r）這個回文串中和他位置對稱的 d [ j ]

因為在回文串中，所以 d [ i ] 和 d[ j ] 兩邊一定長度內(nèi)的字符是相同的

而這個一定長度就是，以 s [ j ] 為中心的回文串的長度，可能超過了（l，r）的范圍

所以不能看作回文串，只有在這個范圍內(nèi)才能看作回文串

所以我們能夠借用這個因素得到的 d [ i ] 兩邊的回文串長度就是min( d [ j ] , j + 1 - r )

得到這個長度之后，我們?yōu)榱说玫阶罱K答案，還需要繼續(xù)擴展 以 s [ i ] 為中心的回文串

所以用樸素算法繼續(xù)擴展

在擴展過程中，如果以 s [ i ] 為中心的回文串的最右邊端點超過了 r?

我們就需要更新? l , r ，保證他們所代表的意義不變

?

然后我們在來討論之前沒有談?wù)摰膬煞N回文串的問題

?

常見的方法是在每兩個字符間都插入一個不可能出現(xiàn)的字符，這樣就能夠?qū)⑺械钠媾甲址D(zhuǎn)化統(tǒng)一

?

也還有另外一種方法

通過訪問雙倍長度，枚舉每一種情況

實際上和插入字符類似，只不過是把字符插入這種操作

通過數(shù)字下標(biāo)的形式取代

建議畫圖理解

?

---

?

【復(fù)雜度】

實際上我們可以看出來，至始至終每次都是 r 在不斷的右移，并沒有出現(xiàn)重復(fù)，所以最后的復(fù)雜度和字符串的長度等同

?

?

1 void manacher(char *s,int n,int *d) 2 { 3 d[0] = 1; 4 for (int i = 1,j = 0; i < (n << 1) - 1; i++) 5 { 6 int p = i >> 1, q = i - p; 7 int r = ((j + 1) >> 1) + d[j] - 1; 8 if (r < q) 9 d[i] = 0; 10 else 11 d[i] = min(r - q + 1, d[(j << 1) - i]); 12 while (0 <= p - d[i] && q + d[i] < n && s[p - d[i]] == s[q + d[i]]) 13 d[i]++; 14 if (q + d[i] - 1 > r) 15 j = i; 16 } 17 } void manacher(char *s,int n,int *d) {d[0] = 1;for (int i = 1,j = 0; i < (n << 1) - 1; i++){int p = i >> 1, q = i - p;int r = ((j + 1) >> 1) + d[j] - 1;if (r < q)d[i] = 0;elsed[i] = min(r - q + 1, d[(j << 1) - i]);while (0 <= p - d[i] && q + d[i] < n && s[p - d[i]] == s[q + d[i]])d[i]++;if (q + d[i] - 1 > r)j = i;} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/rentu/p/11323543.html

總結(jié)

以上是生活随笔為你收集整理的算法学习：manacher的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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