用途

• 求最長(zhǎng)回文串， 過程中更新$max(Maxlen，RL[i]?1)$
• 求回文串的數(shù)量，${\sum }_{i=0}^{len}\frac{RL[i]}{2}$

$RL[i]$ ：關(guān)于i的回文半徑
$MaxRight$：pos能到達(dá)的最右端的位置
$MaxLen$：記錄答案

• 首先在原字符串中插入字符“#”
  例如：“abba” -> "#a#b#b#a#"這樣不影響回文串，好處是可以同時(shí)解決長(zhǎng)度為奇偶的字符串，而且(回文半徑 - 1)就是原來的回文串長(zhǎng)度
• 問題轉(zhuǎn)化為如何高效的求每個(gè)字符的回文串半徑，當(dāng)我們知道pos能到達(dá)的最右端位置$MaxRight$，我們繼續(xù)向后枚舉字符串求它的回文半徑，我們關(guān)心的是i這個(gè)位置是在MaxRight的左邊還是右邊， 在左邊分為兩種情況，右邊一種情況。
• 求出來最小值之后再向兩邊擴(kuò)展得到最長(zhǎng)的回文半徑， 然后更新$pos$，$MaxRight$。

int RL[maxn << 1]; int Manacher(string s) {string t;for (int i = 0; i < (int)s.size(); ++i) {t += s[i];t += '#';}s = "#" + t;int MaxRight = 0, pos = 0, MaxLen = 0;for (int i = 0; i < (int)s.size(); ++i) {if (i < MaxRight) RL[i] = min(RL[2 * pos - i], MaxRight - i + 1); // 好多這里寫的是 MaxRight - i，個(gè)人感覺根據(jù)算法思想應(yīng)該+1計(jì)算長(zhǎng)度。else RL[i] = 1;int l = i - RL[i];int r = i + RL[i];while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {RL[i] += 1;l = i - RL[i];r = i + RL[i];}if (RL[i] + i - 1 > MaxRight) {MaxRight = RL[i] + i - 1;pos = i;}MaxLen = max(MaxLen, RL[i]);}return MaxLen - 1; } int RL[maxn << 1]; char s[maxn], t[maxn << 1]; int Manacher(char *s) {if (s[strlen(s) - 1] == '\n') s[strlen(s) - 1] = '\0';int lens = strlen(s), len = 0;t[len++] = '#';for (int i = 0; i < lens; ++i) {t[len++] = s[i];t[len++] = '#';}int MaxRight = 0, pos = 0, MaxLen = 0;for (int i = 0; i < len; ++i) {if (i < MaxRight) RL[i] = min(RL[2 * pos - i], MaxRight - i + 1); // 好多這里寫的是 MaxRight - i，個(gè)人感覺根據(jù)算法思想應(yīng)該+1計(jì)算長(zhǎng)度。else RL[i] = 1;int l = i - RL[i];int r = i + RL[i];while (l >= 0 && r < len && t[l] == t[r]) {RL[i] += 1;l = i - RL[i];r = i + RL[i];}if (RL[i] + i - 1 > MaxRight) {MaxRight = RL[i] + i - 1;pos = i;}MaxLen = max(MaxLen, RL[i]);}return MaxLen - 1; }

總結(jié)

以上是生活随笔為你收集整理的Manacher 最长回文子串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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