本篇講解manacher算法，大家在學(xué)習(xí)之前，提前了解一下兩個字符串相算法——kmp和拓展kmp，這些算法都是字符串算法。相對于前面介紹的兩個算法，Manacher算法的應(yīng)用范圍要狹窄得多，但是它的思想和拓展kmp算法有很多共通支出，所以在這里介紹一下。Manacher算法是查找一個字符串的最長回文子串的線性算法。

在介紹算法之前，首先介紹一下什么是回文串，所謂回文串，簡單來說就是正著讀和反著讀都是一樣的字符串，比如abba，noon等等，一個字符串的最長回文子串即為這個字符串的子串中，是回文串的最長的那個。

計算字符串的最長回文字串最簡單的算法就是枚舉該字符串的每一個子串，并且判斷這個子串是否為回文串，這個算法的時間復(fù)雜度為O(n^3)的，顯然無法令人滿意，稍微優(yōu)化的一個算法是枚舉回文串的中點，這里要分為兩種情況，一種是回文串長度是奇數(shù)的情況，另一種是回文串長度是偶數(shù)的情況，枚舉中點再判斷是否是回文串，這樣能把算法的時間復(fù)雜度降為O(n^2)，但是當n比較大的時候仍然無法令人滿意，Manacher算法可以在線性時間復(fù)雜度內(nèi)求出一個字符串的最長回文字串，達到了理論上的下界。

1. Manacher算法原理與實現(xiàn)

下面介紹Manacher算法的原理與步驟。

首先，Manacher算法提供了一種巧妙地辦法，將長度為奇數(shù)的回文串和長度為偶數(shù)的回文串一起考慮，具體做法是，在原字符串的每個相鄰兩個字符中間插入一個分隔符，同時在首尾也要添加一個分隔符，分隔符的要求是不在原串中出現(xiàn)，一般情況下可以用#號。下面舉一個例子：

（1）Len數(shù)組簡介與性質(zhì)

Manacher算法用一個輔助數(shù)組Len[i]表示以字符T[i]為中心的最長回文字串的最右字符到T[i]的長度，比如以T[i]為中心的最長回文字串是T[l,r],那么Len[i]=r-i+1。

對于上面的例子，可以得出Len[i]數(shù)組為:

Len數(shù)組有一個性質(zhì)，那就是Len[i]-1就是該回文子串在原字符串S中的長度，至于證明，首先在轉(zhuǎn)換得到的字符串T中，所有的回文字串的長度都為奇數(shù)，那么對于以T[i]為中心的最長回文字串，其長度就為2*Len[i]-1,經(jīng)過觀察可知，T中所有的回文子串，其中分隔符的數(shù)量一定比其他字符的數(shù)量多1，也就是有Len[i]個分隔符，剩下Len[i]-1個字符來自原字符串，所以該回文串在原字符串中的長度就為Len[i]-1。

有了這個性質(zhì)，那么原問題就轉(zhuǎn)化為求所有的Len[i]。下面介紹如何在線性時間復(fù)雜度內(nèi)求出所有的Len。

（2）Len數(shù)組的計算

首先從左往右依次計算Len[i]，當計算Len[i]時，Len[j](0<=j<i)已經(jīng)計算完畢。設(shè)P為之前計算中最長回文子串的右端點的最大值，并且設(shè)取得這個最大值的位置為po，分兩種情況：

第一種情況：i<=P

那么找到i相對于po的對稱位置，設(shè)為j，那么如果Len[j]<P-i，如下圖：

那么說明以j為中心的回文串一定在以po為中心的回文串的內(nèi)部，且j和i關(guān)于位置po對稱，由回文串的定義可知，一個回文串反過來還是一個回文串，所以以i為中心的回文串的長度至少和以j為中心的回文串一樣，即Len[i]>=Len[j]。因為Len[j]<P-i,所以說i+Len[j]<P。由對稱性可知Len[i]=Len[j]。

如果Len[j]>=P-i，由對稱性，說明以i為中心的回文串可能會延伸到P之外，而大于P的部分我們還沒有進行匹配，所以要從P+1位置開始一個一個進行匹配，直到發(fā)生失配，從而更新P和對應(yīng)的po以及Len[i]。

第二種情況: i>P

如果i比P還要大，說明對于中點為i的回文串還一點都沒有匹配，這個時候，就只能老老實實地一個一個匹配了，匹配完成后要更新P的位置和對應(yīng)的po以及Len[i]。

2.時間復(fù)雜度分析

Manacher算法的時間復(fù)雜度分析和Z算法類似，因為算法只有遇到還沒有匹配的位置時才進行匹配，已經(jīng)匹配過的位置不再進行匹配，所以對于T字符串中的每一個位置，只進行一次匹配，所以Manacher算法的總體時間復(fù)雜度為O(n)，其中n為T字符串的長度，由于T的長度事實上是S的兩倍，所以時間復(fù)雜度依然是線性的。

下面是算法的實現(xiàn)，注意，為了避免更新P的時候?qū)е略浇纾覀冊谧址甌的前增加一個特殊字符，比如說‘$’,所以算法中字符串是從1開始的。

const int maxn=1000010;
char str[maxn];//原字符串
char tmp[maxn<<1];//轉(zhuǎn)換后的字符串
int Len[maxn<<1];
//轉(zhuǎn)換原始串
int INIT(char *st)
{
    int i,len=strlen(st);
    tmp[0]='@';//字符串開頭增加一個特殊字符，防止越界
    for(i=1;i<=2*len;i+=2)
    {
        tmp[i]='#';
        tmp[i+1]=st[i/2];
    }
    tmp[2*len+1]='#';
    tmp[2*len+2]='$';//字符串結(jié)尾加一個字符，防止越界
    tmp[2*len+3]=0;
    return 2*len+1;//返回轉(zhuǎn)換字符串的長度
}
//Manacher算法計算過程
int MANACHER(char *st,int len)
{
     int mx=0,ans=0,po=0;//mx即為當前計算回文串最右邊字符的最大值
     for(int i=1;i<=len;i++)
     {
         if(mx>i)
         Len[i]=min(mx-i,Len[2*po-i]);//在Len[j]和mx-i中取個小
         else
         Len[i]=1;//如果i>=mx，要從頭開始匹配
         while(st[i-Len[i]]==st[i+Len[i]])
         Len[i]++;
         if(Len[i]+i>mx)//若新計算的回文串右端點位置大于mx，要更新po和mx的值
         {
             mx=Len[i]+i;
             po=i;
         }
         ans=max(ans,Len[i]);
     }
     return ans-1;//返回Len[i]中的最大值-1即為原串的最長回文子串額長度 
  }