HDu 3068最長回文(manacherアルゴリズム)

manacherアルゴリズム
回文列定義:「回文列」は、「level」や「noon」など、正読みと逆読みが同じ文字列です.
回文サブストリングは、その名の通り、文字列の中で回文の性質を満たすサブストリングである.
よくいくつかのテーマが回文の子列をめぐって討論して、最も長い回文の子列の長さを求めます.素朴アルゴリズムは各文字を中心に両側に順次拡張されているが、明らかにこの複雑さはO(N^2)であり、文字列の問題についてよく用いられるアルゴリズムはKMP、接尾辞配列、ACオートマチックであり、この問題は拡張KMPを利用して解くことができ、その時間的複雑さも速いO(N*logn)である.しかし,今日筆者は,時間的複雑度O(n)のエコーサブストリングに特化したアルゴリズムを紹介する.これがmanacherアルゴリズムである.
文字列を求める際にそのパリティを判断する必要があることはよく知られているが,abaとabbaを求めるアルゴリズムにはわずかな差がある.しかし、このアルゴリズムは簡単な処理を行い、奇数長の回文列と偶数長の回文列を巧みに統一的に考慮した.つまり、隣接する文字の間に区切り記号を挿入し、列の先頭と末尾も加えなければならない.もちろん、この区切り記号は元の列に現れず、一般的には「#」や「$」などの文字を使うことができる.例:
原串:abaab
新しい列:#a#b#a#a#b#
これにより,元の奇数長文字列は奇数長であり,偶数長も‘#’を中心とした奇数文字列となる.
次にアルゴリズムの中心思想として,各文字を中心とした最長回文半径,すなわちP[i]を1つの補助配列Pで記録し,Str[i]文字を中心とした最長回文列半径を記録する.P[i]の最小値は1であり、このとき回文列はStr[i]そのものである.
上記の例について、次のようにP配列を書くことができます.
新しい列:#a#b#a#a#b#
P[] : 1 2 1 4 1 2 5 2 1 2 1
P[i]−1がStr[i]を中心とした回文列の原列における長さであることを証明できる.
証明:
1、明らかにL=2*P[i]-1は新しい列の中でStr[i]を中心として最も長い回文列の長さである.
2、Str[i]を中心とした文字列は必ず#の先頭と末尾である.例えば「#b#b#」や「#b#a#b#」であるから、Lから一番前または最後の「#」を減算する文字は元の列の長さの2倍である.すなわち、元の列の長さは(L-1)/2であり、簡略化されたP[i]-1である.証拠を得る.
P配列を前から順に求めるとよいが,ここではDP(ダイナミックプランニング)の考え方,すなわちP[i]を求める際に,前のP[]値が得られており,回文列の特殊な性質を利用して大きな最適化が可能である.
P[i]を両側に拡張する際に配列が境界を越える可能性を防止するために、配列の一番前と一番後ろに特殊文字を追加し、P[0]='$'の最後の位置を'0'にデフォルト設定し、特殊な処理を必要としないようにする必要があります.さらに,iを求める前の文字列にMaxid変数を記録し,最右端の位置まで延長するとともに,このMaxidのid値をid記録でとる.次の言葉により、アルゴリズムは不要な重複マッチングを多く回避します.

if(MaxId>i)
{
    p[i]=Min(p[2*id-i],MaxId-i);
}

では、この言葉はどのようにして得られたのか、実は回文列の対称性を利用して、次の図のように、
j=2*id-1はiのidについての対称点であり、対称性により、P[j]の回文列もi側に対称になることができるが、P[j]の回文列が対称になってからMaxIdを超えると、超えた部分は対称にならないので、以下の図のように、ここでP[i]が下限となるのは両者のうち小さい者であり、p[i]=Min(p[2*id-i],MaxId-i)である.
アルゴリズムの有効比較回数はMaxId回であるため,このアルゴリズムの時間的複雑度はO(n)である.

#include<stdio.h>
#include<string.h>
const int N=110005;
int min(int a,int b)
{
    return a<b?a:b;
}
char str[N<<1];
int p[N<<1];
int Manacher(char *s)
{
    int i,len=strlen(s),Len;
    int id,Max,Size;
    str[0]='$';
    str[1]='#';
    for(i=1;i<=len;i++)
    {
        str[i<<1]=s[i-1];
        str[(i<<1)+1]='#';
    }
    Len=i<<1;
    str[Len]='\0';
    Max=Size=0;
    for(i = 1; i < Len; i++)
    {
        if(Size>i)
        {
            p[i]=min(p[2*id-i],Size-i);
        }
        else
        {
            p[i]=1;
        }
        while(str[i+p[i]]==str[i-p[i]])
        {
            p[i]++;
        }
        if(p[i]+i>Size)
        {
            Size=p[i]+i;
            id=i;
        }
        if(p[i]>Max)
        {
            Max=p[i];
        }
    }
    return Max-1;
}
int main()
{
    char s[N];
    while(~scanf("%s",s))
    {
        printf("%d
",Manacher(s));
    }
    return 0;
}