對應letecode鏈接：
https://leetcode-cn.com/problems/longest-palindromic-substring/
題目描述：
給你一個字串 s，找到 s 中最長的回文子串，
示例 1：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案，
示例 2：輸入：s = "cbbd"
輸出："bb"
示例 3：輸入：s = "a"
輸出："a"
示例 4：輸入：s = "ac"
輸出："a"
首先回文串有兩種形式：
一種是奇數的比如
"aba"，一種是偶數的比如"abba"
如果我們單個字符為中心向兩邊擴散在這種情況下就會出現問題長度為偶數的回文:"abba"
首先我們以首字符a為中心向兩邊擴散得得到的最長回文字串的長度為1也就是a.我們在已下一個字符b為中心括的時候長度也為1下一個b為中心括的時候長度也為1最終我們求到的最長長回文字串的長度為1.但實際上字串本身就是回文字串這是因為他的對稱軸是在一個虛的位置，
Manacher為了解決這個問題會在每個字符之間都會插入一個特殊字符，并且兩邊也會插入，這個特殊字符要保證不能是原字串中的字符，這樣無論原來字串長度是奇數還是偶數，添加之后長度都會變成奇數，例如：
“#a#b#a#"(長度為7）
"#a#b#b#a#（長度為9）
在這里所加入的特殊字符要不要求是原串中沒有出現的字符呢？答案是并不一定，特殊字符是可以隨意，這是為什么因為在括散的程序中因為不會出現特殊字符和原來字串中的字符相比較的情況，特殊字符只是起到輔助作用不會影響到最終的結果
在這里我們引入一個變數叫回文半徑，通過添加特殊字符，原來字串長度無論是奇數還是偶數最終都會變為奇數，因為特殊字符的參考，改變之后的字串的所有回文子串長度一定都是奇數，并且回文子串的第一個和最后一個字符一定是你添加的那個特殊字符，其實很好證明
如果原來回文子串的長度是奇數，通過中間插入特殊字符，特殊字符的個數必定是偶數，在加上兩邊的特殊字符，長度必然是奇數
如果原來回文子串的長度是偶數，通過中間插入特殊字符，特殊字符的個數必定是奇數，在加上兩邊的特殊字符，長度必然是奇數
因為添加特殊字符之后所有回文子串的長度都是奇數，我們定義回文子串最中間的那個字符到回文子串最左邊或者最右邊的長度叫回文半徑，
比如字串
"babad"在添加特殊字符之后每個字符的回文半徑：
搞懂了這個我們再來看一下最長回文子串該怎么求，在上面我們講過中心擴散法，我們會以每一個字符（中間會過濾掉重復的）為中心往兩邊擴散，如果以當前字符為中心往兩邊擴散計算完的時候，到下一個字符在往兩邊擴散的時候還要重新計算，那么有沒有一種方法不用重新計算，而利用之前計算的結果呢，答案是肯定的，
假設當前字符s[maxCenter]為回文中心的最大回文長度為是從left到maxRight如果我們想求以字符
s[i]為回文中心的最大回文長度，我們只需要找到i關于maxCenter的對稱點j，看下j的回文長度，因為j已經計算過了，
有以后三種情況：
1.i在maxRight的左邊并且以i關于maxCenter的對稱點j 為回文中心的回文區域在leftmaxRight之內，
2.i在maxRight的左邊并且以i關于maxCenter的對稱點j為回文中心區域最大回文長度的左邊剛好到達left或者超過left
3.如果i在maxRight的右邊
情況一：i在maxRight的左邊并且以i關于maxCenter的對稱點j 為回文中心的回文區域在leftmaxRight之內，
為什什么i對應的回文半徑就等于j對應的回文半徑呢？通過對稱性可知以i的回文半徑至少是以j為回文中心的半徑為什不能在大了？證明：假設已j為回文中心區域左邊界的前一個字符為x，右邊界的后一個字符為y,已i為回文中心區域左邊界的前一個字符為z,右邊界的后一個字符為L，這時就有當時為什么已j為回文中心的區域沒能括的更大了原因只可能是x!=y由對稱關系可得z==y，x==L，所以我們可以推出z!=L證畢，
情況二：
i在maxRight的左邊并且以i關于maxCenter的對稱點j為回文中心區域最大回文長度的左邊剛好到達left或者超過left，如果是超過left那么對應i對應的回文半徑為maxRight-i，如果剛好到達left那么對應回文半徑的答案至少為maxRight-i是否能夠更大就要看maxRight-i的前一個字符和maxRight+i是否相等如果相等那么就能夠更長
情況三：
3.如果i在maxRight的右邊
在這種情況下我們無法利用之前計算的結果，此時我們只能暴力擴
對應代碼：
class Solution { public: string longestPalindrome(string s) { int len = s.length(); if (len < 1) { return ""; } // 預處理 string s1; for (int i = 0; i < len; i++) { s1 += "#"; s1 += s[i]; } s1 += "#"; len = s1.length(); int MaxRight = 0; // 當前訪問到的所有回文子串，所能觸及的最右一個字符的下一個位置 int Center = 0; // MaxRight對應的回文串的對稱軸所在的位置 int MaxRL = 0; // 最大回文串的回文半徑 int MaxCenter = 0; // MaxRL對應的回文串的對稱軸所在的位置 int* RL = new int[len]; // RL[i]表示以第i個字符為對稱軸的回文串的回文半徑 memset(RL, 0, len * sizeof(int)); for (int i = 0; i < len; i++) { RL[i]=MaxRL>i?min(RL[2*Center-i],MaxRL-i):1;//將上序三種情況合并 // 嘗試擴展RL[i]，注意處理邊界 while (i - RL[i] >= 0 // 可以把RL[i]理解為左半徑,即回文串的起始位不能小于0 && i + RL[i] < len // 同上,即回文串的結束位不能大于總長 && s1[i - RL[i]] == s1[i + RL[i]]// 回文串特性，左右擴展，判斷字串是否相同 ) { RL[i]++; } // 更新MaxRight, pos if (RL[i] + i > MaxRight) { MaxRight = RL[i] + i ; Center = i; } // 更新MaxRL, MaxPos if (MaxRL <RL[i]) { MaxRL = RL[i]; MaxCenter = i; } } return s.substr((MaxCenter-MaxRL+1) / 2, MaxRL - 1);//回傳字串 } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/393923.html
標籤：其他
上一篇：（Java）筆記篇---HashMap底層原理決議及HashMap常考面試題
下一篇：【資料結構】鏈表全決議