初学回文オートマトン

回文というものには、いいアルゴリズムがあります.例えばマラ車アルゴリズムは、非常に優れたアルゴリズムです.私もマラ車に関する文章を習ったことがあります.とても簡単で分かりやすいです.しかし、私たちが今日話しているのはマラ車よりも強いアルゴリズム--回文自動機です.回文のオートマトンとACオートマトンはいくつか似ている地方があって、だから兴味のある学友はこの文章を见てACオートマトンを理解することができます
では、今日の本文を始める前に、回文オートマチックをよりよく理解するために、いくつかの配列を定義しなければなりません.
fail[x]:xが不整合になった後にジャンプした自己の最長接尾辞文字列に等しくない.(これはちょっとわかりにくいかもしれませんが、ACオートマチックfailを参照)
len[x]:xを最後とする最長回文サブ列の長さ.
cnt[x]:xで終わる最長回文サブストリングと同じサブストリングの個数
son[x][c]:xと番号付けされたノードが表すエコー列両側に文字cを追加した後になるエコー列の番号
s[x]:x回目に追加された文字(最初はS[0]=-1とし、いずれかの列Sには現れない文字であってもよい).
これらの配列を定義したら、接尾辞オートマチックの構築を開始します.まず,fail[0]=1,len[1]=−1 f a i l[0]=1,l e n[1]=−1の2つの空のノード0と1を構築し,このような設定は後で有用である.次に、文字を読み込んで、それを最後にした最長の回文サブ列の長さを見つけます.このコードは次のとおりです.

ll get_fail(ll p,ll x){
    while(s[x-len[p]-1]!=s[x]) p=fail[p];
    return p;
}

ノードxの最長回文サブ列の長さは、関数len[p]+2 l e n[p]+2である.ある回文サブストリングの左端が新しく追加された文字と同じかどうかを見るため、もし同じであれば、私たちが要求した回文サブストリングであり、異なる場合、私たちは現在の回文ストリングの最長接尾辞回文サブストリングにジャンプし、マッチングを続けます.ACオートマチックに似ているのではないでしょうか.例えば、現在の列がcbbabbである場合、最も長い回文サブ列がbbabbである場合、文字aを追加すると、aはbbabbの左側の文字(c)と比較され、異なることが発見され、bbabbの最も長い接尾辞回文サブ列、すなわちbbにジャンプし、マッチングを継続する.bbの左側の文字はaで、私たちが追加する文字と同じなので、新しく追加したlenはlen(bb)+2=4 l e n(bb)+2=4、つまりサブ列abbaです.次に、そのfail、すなわち現在の列abbaの最長接尾辞サブ列を求めると、bbを持ってaとマッチングを継続し、残念ながらマッチングできないので、一路0にジャンプし、fail[0]=1 f a i l[0]=1なので、点1に着き、len[1]=−1 l e n[1]=−1になり、get g e t_t_に連れて行くfail f a i lではs[x−(−1)−1]=s[x]s[x−(−1)−s[x]=s[x]=s[x]であることが判明し,s[x]=s[x]s[x]=s[x]であることを意味するので,その最長接尾辞文字列はそれ自身bであるため,failを見つけた点につなげておけばよい.fail[now]=son[get_fail(fail[cur],i)][s[i]-'a'];//cur=get_fail(last,i),s[i] 建造の過程は皆さんが自分でいくつかの例を挙げて、コードによって理解することができて、比較的に理解しやすいはずです.コードは次のとおりです.

#include
#define MAXN 300010
#define ll long long
using namespace std;
ll read(){
    char c;ll x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
char s[MAXN];
ll fail[MAXN],son[MAXN][26],len[MAXN],cnt[MAXN];
ll tot,last,cur,ans;
ll newnode(ll x){
    len[tot]=x;
    return tot++;
}
ll get_fail(ll p,ll x){
    while(s[x-len[p]-1]!=s[x]) p=fail[p];
    return p;
}
int main()
{
    scanf("%s",s+1);
    s[0]=-1;fail[0]=1;last=0;
    newnode(0);newnode(-1);
    register int i;
    for(i=1;s[i];i++){
        cur=get_fail(last,i);
        if(!son[cur][s[i]-'a']){
            ll now=newnode(len[cur]+2);
            fail[now]=son[get_fail(fail[cur],i)][s[i]-'a'];
            son[cur][s[i]-'a']=now;
        } 
        cnt[last=son[cur][s[i]-'a']]++;
    }
    for(i=tot-1;i>=0;i--){
        cnt[fail[i]]+=cnt[i];
    }
    return 0;
} 

皆さんにこのブログをお勧めします.詳しい例と図解があります.