🌠作者：@阿亮joy.
🎆專欄：《數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué)》
🎇座右銘：每個優(yōu)秀的人都有一段沉默的時光，那段時光是付出了很多努力卻得不到結(jié)果的日子，我們把它叫做扎根

👉前言👈

如果給定一個字符串 str，如何求解該字符串的最長回文子串（注：子串必須是連續(xù)的，子序列不要求連續(xù)）。如字符 str 為 abc12320d1，其最長回文子串是 232，而不是 回文子序列 12321。如果一個字符串是回文串，那么該字符串一定有個對稱軸，使得左右兩邊的字符是對稱的。比如：字符串 abcba 的對稱軸是字符 c（實軸），字符串 abba 的對稱軸是一條虛軸（不是關(guān)于某個字符對稱）。

那么我們要求字符串的最長回文子串，我們很容易想到一種暴力的方法：遍歷字符串的每一個字符，從該字符為中心向左右兩邊擴（左邊和右邊的字符相等就擴，不相等就停止），這樣就能得到最長回文子串了。這種方法的時間復(fù)雜度是 O(N^2)，非常的暴力，而且這種方法不能夠解決字符串長度為偶數(shù)的情況。如：字符串 122131221，因為回文串長度為偶數(shù)時，其對稱軸是虛軸，這樣就無法保證每個字符向左右兩邊擴都能得到以該字符為中心的最長回文串。

那如何保證能夠得到偶數(shù)的回文串呢？這就需要學(xué)習(xí)本篇博客要介紹的 Manacher 算法。

👉Manacher 算法👈

Manachar 算法主要是處理字符串中關(guān)于回文串的問題的，它可以在 O(N) 的時間處理出以字符串中每一個字符為中心的回文串半徑，由于將原字符串處理成兩倍長度的新串，在每兩個字符之間加入一個特定的特殊字符，因此原本長度為偶數(shù)的回文串就成了以中間特殊字符為中心的奇數(shù)長度的回文串了。

Manacher 算法提供了一種巧妙的辦法，將長度為奇數(shù)的回文串和長度為偶數(shù)的回文串一起考慮。具體做法是：在原字符串的每個相鄰兩個字符中間插入一個分隔符，同時在首尾也要添加一個分隔符，分隔符可以是原串中的子串，但一般情況下都是使用 # 號作為分隔符。

如果 Manacher 算法也像上圖的做法來求最長回文子串的話，那么它的時間復(fù)雜度也是 O(N^2)，那 Manacher 算法是如何將時間復(fù)雜度優(yōu)化到 O(N) 的呢？我們一起來看一下！

Manacher 算法的優(yōu)化就是通過已知信息來做到時間復(fù)雜度的優(yōu)化。首先，我們需要知道回文半徑和回文直徑的概念。見下圖所示：

知道回文半徑和回文直徑后，我們還需要知道一個概念—— 回文半徑數(shù)組，就是我們將已經(jīng)求得的回文半徑放在數(shù)組中，那么該數(shù)組就被稱為回文半徑數(shù)組。還有最后兩個概念，一個是回文右邊界，另一個是回文中心?；匚闹行谋容^好理解，就是回文串的中心點下標(biāo)?；匚挠疫吔缡且悦總€字符為中心擴出來的回文串的右邊界，它是一個整型。在擴的過程中，如果新生成的回文串的右邊界比原來右邊界還要右，這時候就需要更新回文右邊界；否則不需要更新。如果回文右邊界更新，回文中心就需要更新；而如果回文右邊界沒有更新，回文中心也不需要更新。

知道了上面的全部概念后，我們就來學(xué)習(xí) Manacher 算法。Manacher 算法在更新回文數(shù)組的時候，會遇到兩種情況：字符的下標(biāo)超出回文右邊界和字符的下標(biāo)在回文右邊界的范圍內(nèi)。

當(dāng)字符的下標(biāo)超出回文右邊界時，我們就以該字符為中心向左右暴力兩邊擴，然后更新回文右邊界。

當(dāng)字符的下標(biāo)在回文右邊界的范圍內(nèi)，這時候就可以通過已用的信息（回文數(shù)組）來進行優(yōu)化了。

字符下標(biāo)在回文右邊界內(nèi)這種情況又可以根據(jù) i’ 回文區(qū)域的不同分為三個小類：

• 第一小類：i’ 的整個回文區(qū)域都在 left 到 right 的范圍內(nèi)

• 第二小類：i’ 回文區(qū)域的左邊界小于 left

• 第三小類：i’ 回文區(qū)域的左邊界等于 left

Manacher 算法偽代碼

// 返回值是回文半徑數(shù)組
vector<int> Manacher(string& s)
{// 1221 -> #1#2#1#2#1#s 經(jīng)過處理變成了 strvector<int> pArr(str.size(), 0);	// 回文半徑數(shù)組int right = -1;	//回文右邊界int center = -1;	// 回文中心for(int i = 0; i < str.size(); ++i){if(i在right的外部){以i為中心，向左右兩邊暴力擴，回文右邊界right變大}else{if(i'的回文區(qū)域在left到right范圍內(nèi)){pArr[i] = pArr[2 * center - i]	// 堆成性質(zhì)}else if(i'回文區(qū)域的左邊界小于left){pArr[i] = right  + 1 - i;	// 加一的原因是回文半徑需要加上中心點i}else	// i'回文區(qū)域的左邊界等于left{從right范圍之外的字符開始往外擴，然后確定回文半徑pArr[i]第一次擴失敗了，回文右邊界right不變否則，回文右邊界right變大}}}return pArr;
}

很顯然，Manacher 算法的時間復(fù)雜度是 O(N)。

👉最長回文子串👈

根據(jù) Manacher 算法的偽代碼，我們可以改成以下的精簡版本的代碼

class Solution 
{
public:string longestPalindrome(string s) {// babad --> #b#a#b#a#d// 加入分隔符#string tmp = "#";for(auto ch : s){tmp += ch;tmp += "#";}vector<int> pArr(tmp.size(), 0);    // 回文半徑數(shù)組int center = -1;   // 回文中心int right = -1;    // 回文右邊界的再往右一個位置,最右的回文區(qū)域是R-1位置int start = 0;     // 最長回文子串的左邊界int end = -1;      // 最長回文子串的右邊界int Max = INT_MIN; // 最長回文子串的半徑,即最長回文串的直徑 / 2 + 1// 那么 Max - 1 就是原字符串的最長回文子串的長度// 每個位置都要求回文半徑int size = tmp.size();for(int i = 0; i < size; ++i){// i至少的回文區(qū)域,先更新給pArr[i]// 不需要擴就能知道i的最小回文區(qū)域// i在right外時,需要暴力擴,i的回文區(qū)域至少包括自己// i在right內(nèi),第一小類和第二小類是能夠直接拿到的// 對于第一和第二小類,i的回文半徑是(pArr[2 * center - 1]、right - i)中的較小值pArr[i] = right > i ? min(pArr[2 * center - i], right - i) : 1;// 第三小類是需要向左右兩邊擴才能確定的往,循環(huán)條件保證往外擴時不越界// 第一和第二小類第一次擴就會擴失敗while(i + pArr[i] < size && i - pArr[i] > -1){if(tmp[i + pArr[i]] == tmp[i - pArr[i]])++pArr[i];elsebreak;}// 更新回文右邊界和回文中心if(i + pArr[i] > right){right = i + pArr[i];center = i;}// 注：i+pArr[i]大于right并不意味著以i為中心的回文子串就是最長的回文子串// 而如果以i為中心的回文子串就是最長的子串,那么i+pArr[i]一定大于right// 更新最長回文子串的半徑、左邊界和右邊界if(pArr[i] > Max){Max = pArr[i];// 因為right是回文右邊界的下一個位置,且最長回文子串// 的左邊界加右邊界等于兩倍的center,所以可以推出// start + right - 1 = 2 * centerstart = 2 * center + 1 - right;end = right - 1;}}// 將最長回文子串還原出來// Max - 1 和 (end + 1 - start) / 2都是最長回文子串的長度string ret;for(int i = start; i <= end; ++i){if(tmp[i] != '#')ret += tmp[i];}return ret;}
};

👉總結(jié)👈

本篇博客主要講解什么是 Manacher 算法以及 Manacher 算法是如何求解最長回文子串的。那么以上就是本篇博客的全部內(nèi)容了，如果大家覺得有收獲的話，可以點個三連支持一下！謝謝大家！💖💝??