Manacher算法學習筆記 | LeetCode#5

Manacher算法學習筆記

DECLARATION

引用來源：https://www.cnblogs.com/grandyang/p/4475985.html

CONTENT

用途：尋找一個字符串的最長回文子串
時間復雜度：O(N)
算法步驟：
1.添加特殊字符

由于回文串的長度可奇可偶，比如"bob"是奇數形式的回文，"noon"就是偶數形式的回文，馬拉車算法的第一步是預處理，做法是在每一個字符的左右都加上一個特殊字符，比如加上'#'，那么

bob --> #b#o#b#

noon --> #n#o#o#n#

這樣做的好處是不論原字符串是奇數還是偶數個，處理之后得到的字符串的個數都是奇數個，這樣就不用分情況討論了，而可以一起搞定。

2.求每個回文子串的半徑

我們還需要和處理后的字符串t等長的數組p，其中p[i]表示以t[i]字符為中心的回文子串的半徑，若p[i] = 1，則該回文子串就是t[i]本身。

最長子串的長度是半徑減1，起始位置是中間位置減去半徑再除以2。

如何求p數組，需要新增兩個輔助變量mx和id，其中id為能延伸到最右端的位置的那個回文子串的中心點位置，mx是回文串能延伸到的最右端的位置，這個算法的最核心的一行如下：
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

代碼實現：
Leetcode #5

class Solution {
public:string longestPalindrome(string s) {// Insert '#'string t = "$#";for (int i = 0; i < s.size(); ++i) {t += s[i];t += "#";}// Process tvector<int> p(t.size(), 0);int mx = 0, id = 0, resLen = 0, resCenter = 0;for (int i = 1; i < t.size(); ++i) {p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;while (t[i + p[i]] == t[i - p[i]]) ++p[i];if (mx < i + p[i]) { //update mx & idmx = i + p[i];id = i;}if (resLen < p[i]) { //update resLen & resCenterresLen = p[i];resCenter = i;}}return s.substr((resCenter - resLen) / 2, resLen - 1);}
};