Manaherアルゴリズムのまとめ

  Manacher  ，                     。
              ， O(n)
          

1）   

                                 (             ，   ，   baidu)
 Manacher   ，               ，       s1,             s2.
  ，  s1 = "ababba",      
     s2 = "$#a#b#a#b#b#a#".
    ，      ， s2 ，     ，             。      ，   s2[0] = '$'，                  ，            。        。     P[i] = min(P[2*id]-i),mx-i)          ：
         ，  i=1，id = 0，2*id-i = -1,        。。          。

void init()
{
    int i, j = 2;
    s2[0] = '$', s2[1] = '#';
    
    for(i=0;s1[i];i++)
    {
        s2[j++] = s1[i];
        s2[j++] = '#';
    }
    s2[j] = '\0';
}

2）Manacher  

       ，    Manacher           。
    ，                               ，           。

  ，         P[](  s2   )，     P[i] ，  P[i]              。        P[i]-1                     。　　

//           
      12212321  
     ，    S[] = "$#1#2#2#1#2#3#2#1#";
        P[i]       S[i]            /      （  S[i]，        “  ”     ），  S P     ：
---------------------------------------------------------
S   #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
P   1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
---------------------------------------------------------
(p.s.     ，P[i]-1               ）

               ，          id           ，     mx   id        。
     ，      

void manacher(char* s)
{
    int i, id = 0, mx = 0;
    P[0] = 0;              //P[0]    
    for(i=1;s[i];i++)      //        
    {
        if(mx > i)         //  mx   i ，      ，            blog    ，      
            P[i] = min(P[2*id-i],mx-i);
        else               //  mx i ，         ，           
            P[i] = 1;
        while(s[i + P[i]] == s[i - P[i]])    P[i]++;　　//  
        if(mx < P[i] + i) //       mx  id
        {
            mx = P[i] + i;
            id = i;
        }
    }
}

以下の参照事項を参照してください.http://www.cnblogs.com/BigBallon/p/3816890.html
最後に練習をして上手になります.
hdu 3068 poj 3796 hdu 3294 hdu 4513 hdu 5371(多校7_1003題)
問題番号を解題報告とする.探して&星空の子供