這次要記錄的是一個(gè)經(jīng)典的字符串的題目，也是一個(gè)經(jīng)典的馬拉車(chē)算法的實(shí)踐。相信在很多地方都會(huì)考到或者問(wèn)到這道題目，這道題目也是字符串類(lèi)型中必備的基礎(chǔ)知識(shí)。那么接下來(lái)我們看看題目描述：

回文串是指aba、abba、cccbccc、aaaa這種左右對(duì)稱(chēng)的字符串。
輸入一個(gè)字符串Str，輸出Str里最長(zhǎng)回文子串的長(zhǎng)度。
Input
輸入Str（Str的長(zhǎng)度 <= 100000)
Output
輸出最長(zhǎng)回文子串的長(zhǎng)度L。
Input示例
daabaac
Output示例
5

接下來(lái)我們直接介紹manacher算法的分析過(guò)程，然后再附上代碼。

• (1) 解決長(zhǎng)度奇偶性帶來(lái)的對(duì)稱(chēng)軸位置問(wèn)題
  Manacher算法首先對(duì)字符串做一個(gè)預(yù)處理，在所有的空隙位置(包括首尾)插入同樣的符號(hào)，要求這個(gè)符號(hào)是不會(huì)在原串中出現(xiàn)的。這樣會(huì)使得所有的串都是奇數(shù)長(zhǎng)度的。以插入#號(hào)為例：

aba ———> #a#b#a#
abba ———> #a#b#b#a#

插入的是同樣的符號(hào)，且符號(hào)不存在于原串，因此子串的回文性不受影響，原來(lái)是回文的串，插完之后還是回文的，原來(lái)不是回文的，依然不會(huì)是回文。

• (2) 解決重復(fù)訪問(wèn)的問(wèn)題
  我們把一個(gè)回文串中最左或最右位置的字符與其對(duì)稱(chēng)軸的距離稱(chēng)為回文半徑。Manacher定義了一個(gè)回文半徑數(shù)組RL，用RL[i]表示以第i個(gè)字符為對(duì)稱(chēng)軸的回文串的回文半徑。我們一般對(duì)字符串從左往右處理，因此這里定義RL[i]為第i個(gè)字符為對(duì)稱(chēng)軸的回文串的最右一個(gè)字符與字符i的距離。對(duì)于上面插入分隔符之后的兩個(gè)串，可以得到RL數(shù)組：

char: # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6

char: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8

上面我們還求了一下RL[i]-1。通過(guò)觀察可以發(fā)現(xiàn)，RL[i]-1的值，正是在原本那個(gè)沒(méi)有插入過(guò)分隔符的串中，以位置i為對(duì)稱(chēng)軸的最長(zhǎng)回文串的長(zhǎng)度。那么只要我們求出了RL數(shù)組，就能得到最長(zhǎng)回文子串的長(zhǎng)度。

于是問(wèn)題變成了，怎樣高效地求的RL數(shù)組?；舅悸肥?em>利用回文串的對(duì)稱(chēng)性，擴(kuò)展回文串

我們?cè)僖胍粋€(gè)輔助變量MaxRight 表示當(dāng)前訪問(wèn)到的所有回文子串，所能觸及的最右一個(gè)字符的位置。另外還要記錄下MaxRight
對(duì)應(yīng)的回文串的對(duì)稱(chēng)軸所在的位置，記為pos。

它們的位置關(guān)系如下。

i在pos位置的示意圖

我們從左往右地訪問(wèn)字符串來(lái)求RL，假設(shè)當(dāng)前訪問(wèn)到的位置為i即要求RL[i]，在對(duì)應(yīng)上圖，i必然是在po右邊的(obviously)因?yàn)槲覀円呀?jīng)求了pos，然后從左到右，所有接下來(lái)的i是在pos的右邊。但我們更關(guān)注的是，i是在MaxRight的左邊還是右邊。我們分情況來(lái)討論。

1）當(dāng)i在MaxRight的左邊

情況1)可以用下圖來(lái)刻畫(huà)：

i在pos右邊

我們知道，圖中兩個(gè)紅色塊之間（包括紅色塊）的串是回文的；并且以i為對(duì)稱(chēng)軸的回文串，是與紅色塊間的回文串有所重疊的。我們找到i關(guān)于pos的對(duì)稱(chēng)位置j，這個(gè)j對(duì)應(yīng)的RL[j]我們是已經(jīng)算過(guò)的。根據(jù)回文串的對(duì)稱(chēng)性，以i為對(duì)稱(chēng)軸的回文串和以j為對(duì)稱(chēng)軸的回文串，有一部分是相同的。這里又有兩種細(xì)分的情況。

1.以j為對(duì)稱(chēng)軸的回文串比較短，短到像下圖這樣。

j回文串很短

這時(shí)我們知道RL[i]至少不會(huì)小于RL[j]（為什么呢？因?yàn)閯e忘了整體是在pos的回文串中，那么i和j以及它的淡藍(lán)色部分都是關(guān)于pos對(duì)稱(chēng)相等的），并且已經(jīng)知道了部分的以i為中心的回文串，于是可以令RL[i]=RL[j]。但是以i為對(duì)稱(chēng)軸的回文串可能實(shí)際上更長(zhǎng)，因此我們?cè)囍詉為對(duì)稱(chēng)軸，繼續(xù)往左右兩邊擴(kuò)展，直到左右兩邊字符不同，或者到達(dá)邊界。

2.以j為對(duì)稱(chēng)軸的回文串很長(zhǎng)，這么長(zhǎng)：

j的回文串很長(zhǎng)

這時(shí)，我們只能確定，兩條藍(lán)線(xiàn)之間的部分（即不超過(guò)MaxRight的部分）是回文的，于是從這個(gè)長(zhǎng)度開(kāi)始，嘗試以i為中心向左右兩邊擴(kuò)展，，直到左右兩邊字符不同，或者到達(dá)邊界。

不論以上哪種情況，之后都要嘗試更新MaxRight和pos，因?yàn)橛锌赡艿玫礁蟮腗axRight。

2）當(dāng)i在MaxRight的右邊

i在maxright右邊

遇到這種情況，說(shuō)明以i為對(duì)稱(chēng)軸的回文串還沒(méi)有任何一個(gè)部分被訪問(wèn)過(guò)，于是只能從i的左右兩邊開(kāi)始嘗試擴(kuò)展了，當(dāng)左右兩邊字符不同，或者到達(dá)字符串邊界時(shí)停止。然后更新MaxRight和pos。

代碼實(shí)現(xiàn)：

#include <iostream>
#include <string>
using namespace std;

int max(int a,int b)
{
    return a>b?a:b;
}

int min(int a,int b)
{
    return a>b?b:a;
}


string init(string s)
{
    string s1="$#";
    int len=s.size();
    int i;
    for(i=0;i<len;i++)
    {
        s1+=s[i];
        s1+="#";
    }

    return s1;
}

int Manacher(string s)
{
    string s1=init(s);

    int mx=0;//最大右邊界
    int pos;//最大回文串的對(duì)稱(chēng)軸
    int len=s1.size();

    int *p=new int [len];//回文最長(zhǎng)半徑數(shù)組 p[i]=k 代表在位置i的回文串的最長(zhǎng)半徑為k
    

    int i;
    int res=0;
    for(i=1;i<len;i++)
    {
        if(mx>i)//i在mx左邊
        {
            p[i]=min(p[2*pos-i],mx-i);
        }
        else//i在mx右邊 必須一個(gè)個(gè)匹配
        {
            p[i]=1;
        }

        while(s1[i-p[i]]==s1[i+p[i]])//上面得到的是初步的p[i]可能以i為對(duì)稱(chēng)軸的回文串更長(zhǎng)需要手動(dòng)檢查
        {
            p[i]++;
        }

        if(i+p[i]>mx)//更新maxright 最大回文串對(duì)稱(chēng)軸位置
        {
            pos=i;
            mx=pos+p[i];
        }

        res=max(res,p[i]-1);
    }

    delete [] p;
    return res;
}

//manacher算法 時(shí)間復(fù)雜度O(N)
int main()
{
    string s;
    cin>>s;
    cout<<Manacher(s)<<endl;
    return 0;
}

我自己的方法：雖然時(shí)間復(fù)雜度先對(duì)manacher算法會(huì)相對(duì)高一點(diǎn)，但是至少能AC。
思路：就是遍歷字符串的每一個(gè)字符，然以當(dāng)前字符串為中心。向兩邊去訪問(wèn)看是否符合回文，并記錄最長(zhǎng)的回文長(zhǎng)度。這時(shí)就要分情況討論，有的是奇數(shù)型的回文，有的是偶數(shù)型的回文串。那么分情況進(jìn)行計(jì)算，然后更新最大值。即可

int main()
{
    string s;
    cin>>s;
    int i;
    int len=s.size();
    int j;
    int cur;
    int res=0;
    int temp=0;
    for(cur=0;cur<len;cur++)
    {
        i=cur;
        j=cur;

        if((cur-1>=0&&s[cur]==s[cur-1])||(cur+1<len&&s[cur]==s[cur+1]))
        {
            while(j<len&&s[j]==s[j+1])
            {
                j++;
            }

            while(i>=0&&s[i]==s[i-1])
            {
                i--;
            }
            
            temp=j-i+1;
            cur=j;
        }
        
        if(i>=0&&j<len&&s[i-1]==s[j+1])
        {
            while(i>=0&&j<len&&s[i-1]==s[j+1])
            {
                i--;
                j++;
            }

            if(i==-1&&j==len)
            {
                temp=len;
            }
            else
            {
                temp=j-i+1;
            }

            cur=j-1;
        }

        res=max(res,temp);
    }

    cout<<res<<endl;
    return 0;

}

算法講解參考：
最長(zhǎng)回文子串——Manacher 算法