"馬拉車"是對manacher(算法作者)的音譯，它的最基礎(chǔ)的用途是以O(shè)(n)的時間復(fù)雜度求出一個字符串的最長回文子串(例如aabacda的最長回文子串是aba)

首先在處理回文問題的時候有一個技巧：由于回文串長度有可能為奇數(shù)也有可能為偶數(shù)，所以原生的回文子串中心不一定在一個字符上?？梢栽诿績蓚€字母之間插入一個特殊字符（比如‘#’），這樣所有的回文串就都變成了以一個字符為回文中心

求最長回文子串的樸素做法是:
按回文串的中心位置進行枚舉（即s[1]到s[n])，計算出每個回文串的最大長度，復(fù)雜度是O(n^2)

假設(shè)以s[i]為中心的最長回文串半徑為r,(即由s[i-r]到s[i+r]這2r+1個字符組成的)，可以得到這樣的信息：
s[i-k]==s[i+k] (0<=k<=r)
s[i-r-1]!=s[i+r+1]
并且由于回文串的對稱性，若已知以s[i-k]為中心的最長回文串b半徑長度為len[i-k],則以s[i+k]為中心的最長回文串半徑長度len[i+k]至少可以取到min(len[i-k],r-k)
于是當(dāng)從左往右遍歷枚舉每個回文子串的中心位置時，若當(dāng)前計算的位置s[i]被它左邊的某個最長回文子串覆蓋到（假設(shè)是以s[p]為中心)，則s[i]不必從s[i+1]、s[i-1]開始判斷，而可以直接從半徑=min(len[2p-i],p+len[p]-i)開始判斷
在算法中每個字符只會被匹配到一次，因此均攤復(fù)雜度是O(n)

而求所有回文子串的個數(shù)同樣可以在馬拉車的遍歷過程中計算出來：
對于以s[i]為中心的最長回文子串來說，已s[i]為中心的所有回文子串的個數(shù)其實就是leni
例如abcba是最長回文子串，則以c為中心的回文串有3個：c bcb abcba

核心代碼如下：

int mx=0,p=0,cnt=0;
memset(len,0,sizeof len);
for(int i=1;i<=n;i++)
{
    if(mx>i)len[i]=min(mx-i,len[2*p-i]);
    else len[i]=1;
    while(s[i-len[i]]==s[i+len[i]])len[i]++;
    if(len[i]+i>mx)mx=len[i]+i,p=i;
    cnt+=len[i]/2;///除以2是因為這里的字符串之間插入了‘#’
}