算法原理

• 最長(zhǎng)回文字符串包括奇數(shù)長(zhǎng)的和偶數(shù)長(zhǎng)的，求的時(shí)候都要分情討論,Manacher算法做了一個(gè)簡(jiǎn)單的處理，很巧妙地把奇數(shù)長(zhǎng)度回文串與偶數(shù)長(zhǎng)度回文串統(tǒng)一考慮，也就是在每個(gè)相鄰的字符之間插入一個(gè)分隔符，串的首尾也要加，當(dāng)然這個(gè)分隔符不能再原串中出現(xiàn)，一般可以用‘#’字符。
  這樣一來，原來的奇數(shù)長(zhǎng)度回文串還是奇數(shù)長(zhǎng)度，偶數(shù)長(zhǎng)度的也變成以‘#’為中心奇數(shù)回文串了。
  其次給每個(gè)字符串首部加一個(gè)題目中不會(huì)出現(xiàn)的字符，避免處理越界問題。（一般加’$’）
  

  
  如圖字符串就是通過算法預(yù)處理得到的新串
  數(shù)組記錄的以 為中間字符的回文串向右能匹配的最大長(zhǎng)度(包括S[i]這個(gè)字符).
  當(dāng)不是所加字符‘#’時(shí)，就是字符串長(zhǎng)度了

• 假設(shè)以i為中心的回文串長(zhǎng)度為,因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=p%5B%20i" alt="p[ i" mathimg="1">]記錄以 為中間字符的回文串向右能匹配的長(zhǎng)度，所以有
  
  又因?yàn)榇藭r(shí)串中加了其他字符#，以為中心的回文串一定是以#開頭和結(jié)尾的，以#為中間字符的就是長(zhǎng)度為偶數(shù)的，以非#號(hào)為中間字符的就是長(zhǎng)度為奇數(shù)的，例如“#b#b#”或“#b#a#b#”所以減去最前或者最后的‘#’字符就是原串中長(zhǎng)度的2倍，即原串長(zhǎng)度為，化簡(jiǎn)的。

算法實(shí)現(xiàn)

• 算法實(shí)現(xiàn)就是要找出數(shù)組,如何找出數(shù)組是關(guān)鍵.

首先從左往右依次計(jì)算，當(dāng)計(jì)算時(shí)，已經(jīng)計(jì)算完畢。設(shè)為之前計(jì)算中最長(zhǎng)回文子串的右端點(diǎn)的最大值，并且設(shè)取得這個(gè)最大值的位置為，分兩種情況：

情況1：

1. 
   那么找到相對(duì)于的對(duì)稱位置，設(shè)為，那么如果
   因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=i%2Bj%3D2*id" alt="i+j=2*id" mathimg="1">,能向左匹配的最左端點(diǎn)的坐標(biāo)是
   所以可知,所以可知
   向如下圖：
   
   
   那么說明以為中心的回文串一定在以為中心的回文串的內(nèi)部，且和關(guān)于位置對(duì)稱,那么意味著以為中間字符的回文串能向右匹配最右端點(diǎn)沒有超過。由回文串的定義可知，一個(gè)回文串反過來還是一個(gè)回文串，所以以i為中心的回文串的長(zhǎng)度至少和以j為中心的回文串一樣，所以。
2. 如果,由對(duì)稱性，說明以為中心的回文串可能會(huì)延伸到之外，而大于的部分我們還沒有進(jìn)行匹配，所以要從位置開始一個(gè)一個(gè)進(jìn)行匹配，直到發(fā)生失配，從而更新和對(duì)應(yīng)的以及。
   
   
   雖然p[j]>mx-i,但是可以保證的是這一段是跟是一樣的，說明以s[i]為中心的回文串至少有這么長(zhǎng)

情況2：

如果i比mx還要大，說明對(duì)于中點(diǎn)為i的回文串還一點(diǎn)都沒有匹配，這個(gè)時(shí)候，就只能老老實(shí)實(shí)地一個(gè)一個(gè)匹配了，匹配完成后要更新的位置和對(duì)應(yīng)的以及。

        int len=strlen(s);
        int mx=0;
        int id=0;
        int res=-1;
        for(int i=len;i>=0;i--)
        {
            s[i*2+2]=s[i];
            s[i*2+1]='#';
        }
        s[0]='$';//加上特殊字符防止越界
        for(int i=0;i<=2*len+1;i++)
        {
            if(mx>i)//mx<i的情況
            {
                p[i]=min(p[2*id-i],mx-i);//比較p[j]大還是mx-i大，取小的
            }
            else//如果i>=mx，要從頭開始匹配
            {
                p[i]=1;
            }
            while(s[i-p[i]]==s[i+p[i]])//一個(gè)一個(gè)比較
            {
                p[i]++;
            }
            if(p[i]+i>mx))//若新計(jì)算的回文串右端點(diǎn)位置大于mx，要更新id和mx的值

            {
                mx=p[i]+i;
                id=i;
            }
            res=max(res,p[i]-1);
        }