簡介

• 在字符串的題目中，有時會遇上 回文串 這樣1個名詞

• 顧名思義，回文串 就是 正讀和反讀都1樣的字符串

• 而 最長回文子串 ，就是在1個字符串的所有子串中，是回文串且長度最長的那個

• 求最長回文子串最普通的方法是 O(N2) ，即枚舉1個點往兩邊擴大

• 但是在有些題目中，N 卻10分的大

• 那末我們就要用到 時間空間復雜度都是 O(N) 的 Manecher 算法

用法

• 在處理回文串時，我們常常會被 中間字符是1個還是兩個 這樣的問題困擾

• 但是在機靈的 Manacher 算法 中，這個問題得到了完善的解決

• 在每兩個字符中間插入1個不會出現的分隔符（如：#）

• 以后在頭尾插入1個還是沒有出現的分隔符（如：*）來避免 While 出界

• 這樣處理起來就方便很多了！

• 設讀入的字符串為 s[i] ，

• 記錄 p[i] 表示 以 s[i] 為中心往兩邊擴大的最大長度

• 視察可知，實際的回文串長度即為當前的 s[i]?1

• 再記錄1個數 id ， p[id]+id表示在 i 位置前所有回文串中能延伸到的最右真個位置

• 以下圖：

• 算法核心就是：

• if(p[id]+id>i) p[i]=min(p[id?2?i],p[id]+id?i); else p[i]=1;

• 當之前所有回文串中能延伸到的最右端覆蓋過 i 時，則取最小值，否則 p[i]=1 ，及自己本身

• 這樣不斷保護 p[i] 和 id ，就可以在 O(N) 內求出 最長回文子串 了！

• 至于為何時間是線性的，由于最有端 p[id]+id 最多只能移動 N 次，

• 有效移動的操作就嚴格線性啦！！

• 下面附上模板：

void Manacher()
{
    scanf("%s",s);
    int len=strlen(s);
    for(int i=len;i>=0;i--)
    {
        int k=i*2+1;
        s[k+1]=s[i],s[k]='#';
    }//插入分隔符
    len*=2;
    s[ans=id=0]='*';
    for(int i=2;i<=len;i++)
    {
        if(p[id]+id>i) p[i]=min(p[id*2-i],p[id]+id-i); else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) p[i]++;
        if(p[i]+i>p[id]+id) id=i;
        if(p[i]>ans) ans=p[i];
    }//處理、計算
}

• 注釋：s[i]，p[i]，id 如題意義，ans 表示 最長回文子串 的長度，而 len 是原串長度

總結

• 這個 Manacher 算法效力極高，時間空間都是 O(N) 線性的

• 再者代碼極短，所以使用起來10分方便，應多多使用！！！