LeetCode- 5 Longest Palindromic Substring

計算最長回文子串：manacher算法

題目：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
           

Example:

Input: "cbbd"

Output: "bb"
           

以下字元串中的空格隻是為了看起來友善。

1. 回文串分為奇數長度的串和偶數長度的串。

   a b c b c len = 5

   a b c c b c len = 6

   為了避免分别考慮這兩種情況。manacher算法通過采用預處理的方式。

   預處理：插入特殊字元（原串中不存在的字元）

   原串：a b c b c len = 5

   預處理後：# a # b # c # b # c # Len = 52 +1 = 11

   原串：a b c c b c len = 6

   預處理後：# a # b # c # b # c # Len = 62 +1 = 13

   可以發現預處理後，串的長度都變成了奇數（預處理可以看成在串的每個字元前面加上"#"，再在串的末尾加上一個"#’,是以預處理後的長度為Len= 2*len +1，永遠都是奇數）

2. 回文串的表示方法 ：采用pos + len的方法。

   maxpos指回文串的中心位置的下标，maxlen指回文串的單向長度

   原串：a b c b c

   pos = 2（注意是原串的下标）

   len = 5（原串中回文串的長度）

   預處理後的串：# a # b # c # b # c #

   maxpos = 5（預處理後的中心位置的下标，注意是下标，從0開始）

   maxlen = 6（預處理後的單向長度，注意是長度，從1開始）

   可以發現：

   pos = maxpos / 2;

   maxlen = len - 1;

   我們就可以根據預處理後求出的回文串對應的原串的長度和下标了

3. 得到原串的長度和下标後，我們就可以計算原串中回文串的[begin,end)的值

   原串：e a b c b a f

   pos = 3;（pos：原串中回文串中心位置下标）

   len = 5;（len：原串中回文串的長度）

   begin = pos - len / 2 = 3 - 5/2 = 1 ;

   end = pos + (len + 1) / 2 = 3+ 3 = 6;

   得到 [begin, end) 為[1,6)

4. 下面是manacher算法的主要部分

   對于處理後的串計算一個RL數組（儲存以每一個字元為中心位置的回文串的單向長度，這裡是向右取長度right-length即RL）

   先把RL數組初始化為1，因為至少包括本身.

   如：# a # b # c # b # c #

   對于a：# a # ,是以RL[1] = 2;

   最終RL[11]={1，2，1，2，1，6，1，2，1，2，1}

   maxpos = 5；

   maxlen = RL[maxpos] = 6;

   此時可計算對應的原串的[begin,end)

   原串：a b c b a

   pos = maxpos / 2 = 2;（原串中回文串的中心位置下标）

   此時可得到對應的原串中[begin,end)的值：

   begin = pos - len / 2 = 2 - 2 = 0;

   end = pos + (len + 1)/2 = 2 +3= 5;

   得到：[0,5)

計算RL數組

從maxpos開始向左右擴充，判斷是否相等，若相等，說明單向長度可以增加1，然後在繼續判斷…

優化manachar算法到O(n)

參考大神的部落格

http://blog.tk-xiong.com/archives/1181

class Solution {
public:
    string manacher(string s)
    {
        //預處理
        string str = "#";
        for(int i = 0; i < s.length(); i++)
        {
            str += s.substr(i,1);
            str += "#";
        }
        
        vector <int> RL(str.length(),1);
        
        int MaxRight = 0;       //向右覆寫的回文串的最右邊的下标
        int MaxRightPos = 0;    //預處理後回文字元串的中心下标
        
        int MaxLen = 0;         //向右單向長度
        int MaxPos = 0;
        
        for(int i = 0;i < str.length(); i++)
        {
            if(i < MaxRight)
            {
                RL[i] = min(RL[MaxRightPos*2 - i],MaxRight - i);
            }
            while((i-RL[i] >= 0) && (i+RL[i] < str.length()) && str[i+RL[i]] == str[i-RL[i]])
            {
                RL[i] += 1;
            }
        
            //更新回文串最右邊下标MaxRight。減1是因為RL[i]包括了i本身占了1位
            if(i+RL[i]-1 > MaxRight)
            {
                MaxRight = i+RL[i]-1;
                MaxRightPos = i;
            }
            
            //更新最長回文串
            if(RL[i] >MaxLen)
            {
                MaxLen = RL[i];
                MaxPos = i;
            }
        }

        int pos = MaxPos / 2;
        int len = MaxLen - 1;
        
        int begin = pos - len / 2;
        string rt = s.substr(begin,len);
        
        return rt;
    }


    string longestPalindrome(string s) 
    {
        return manacher(s);
    }
};