Suffix Automaton についての概要

Suffix Automaton（SAM）は文字列アルゴリズムであり、部分文字列に関する問題を効率的に解くことを可能にします。

例えば：

• 異なる部分文字列の数
• 辞書順で第 \(k\) 番目の部分文字列

前提知識：

• AC自動機
• サフィックス配列（学ぶ必要はない）

複数の文字列を扱う際にはどのようなアルゴリズムがありますか？

最も基本的な手法は trie木です。すべての文字列を木に格納することで、任意の文字列を効率的に検索できます。

マッチングを行う場合、KMPの考え方を応用してtrie木にfail木を構築することで、文字列マッチング問題を効率的に解決できます。これがAC自動機です。

しかし欠点も明確です：trie木に格納される文字列はすべて接頭辞として扱われます。したがって、ある文字列が他の文字列の部分文字列として出現するかどうかを確認するには、すべての部分文字列をAC自動機に構築する必要があります。これは明らかに計算量が膨大です。

AC自動機は接頭辞を格納するので、代わりに各接尾辞を追加すればよいですが、この場合計算量は \(O(n^2)\) になります。

例えば文字列 abaab に対して、以下の図のような構造を得ることができます。

しかし、このような構造ではノードの使用が非常に無駄なので、別の方法を採用する必要があります。

ここから本題に入り、SAMとは何か、どのように構築するかを見ていきます。

文字列 \(S\) とその部分文字列 \(T\) を考え、\(\text{endpos}(T)\) を \(S\) 内での \(T\) の出現位置の右端点の集合と定義します。例えば \(S=abaab\) の場合、\(\text{endpos}(ab)=\{2,5\}\) となります。

いくつか重要な性質があります。

• 2つの部分文字列 \(A,B\) が \(\text{endpos}(A)=\text{endpos}(B)\) を満たし、\(|A|\le |B|\) であれば、\(A\) は \(B\) の部分文字列であり、かつ \(B\) の接尾辞である。

証明は簡単です。各出現位置において \(A\) が存在すれば \(B\) も存在するため、\(A\) は \(B\) の接尾辞であることがわかります。

• \(\text{endpos}(A)\) と \(\text{endpos}(B)\) は含まれる関係または共通部分を持たず、交差することはありません。

証明も簡単です。もし交差していた場合、一方が他方の接尾辞になるため、包含関係にあります。

次に、Suffix Automatonの構築方法を説明します。

すべての \(\text{endpos}(A)\) が同じ部分文字列 \(A\) を一つのノードにまとめて、等価クラスとして扱い、それらの関係を構築します。

• 各等価クラスの最長文字列の長さを \(len\)、最短を \(minlen\) とすると、長さが \([minlen,len]\) の文字列はすべてこの等価クラスに含まれ、最長文字列の接尾辞として現れます。
• \(\text{endpos}(B)\) が \(\text{endpos}(A)\) のサブセットであれば、\(B\) が属する等価クラスは \(A\) が属する等価クラスに接続され、最終的に木構造になります。

これは簡単です。大集合からその部分集合への接続であり、部分集合同士には共通部分がないため、最終的に木構造になり、各ノードの子ノードの集合は自分自身と一致します。

例えば abaab に対して以下の木構造を作ることができます：

このようにして、すべての部分文字列を効率的に木構造に格納できます。

• この木のサイズは \(O(n)\) です。

\(n\) 個のノードが結合され、最大 \(n-1\) 回の結合が行われるためです。

続いて、Suffix Automatonの構築方法について説明します。

このアルゴリズムはオンラインであり、各文字の挿入は \(O(1)\) 時間で可能です。

SAMでは以下の情報を各ノードに保持します：

• \(fa\)：親ノード、つまり後続リンク。
• \(len\)：この等価クラスにおける最長文字列の長さ。
• \(ch[n]\)：trie木と同様に、\(ch[i]\) は現在のノードの後に文字 \(i\) が続く接尾辞の末尾ノードを指す。

\(minlen\) は \(fa\) ノードの \(len\) + 1 で求められます。

新しい文字を追加する際、新たに生成されたすべての接尾辞を自動機に追加します。このとき、\(\text{endpos}(S)=\{n\}\) が得られますが、自動機内にはこの集合に対応するノードが存在しないため、新しいノードを追加し、その \(len\) も即座に決定できます。

次に、親ノードを探索します。これは新しい文字列において \(\text{endpos}(A)\) が \(n\) を含むノードを探します。

このノードは、元の文字列の接尾辞に現在追加された文字 \(c\) を付け加えたものです。

つまり、前回の挿入操作後のノードから上へたどり、\(ch[c]\) が空でない最初のノードを探します。

該当するノードがない場合は、親は初期ノード \(1\) になります。

int p=las,now=las=++tot;tr[now].len=tr[p].len+1;// las は前回の挿入ノード、tot はノード総数
for(;p&&!tr[p].ch[x];p=tr[p].fa)tr[p].ch[x]=now;// 上へたどり、ch[x] が空なら更新
if(!p)tr[now].fa=1;

それ以外の場合、条件を満たすノード \(q\) が存在します。もし \(len_q=len_p+1\) であれば、\(p\) が条件を満たすため、親は \(p\) です。

int q=tr[p].ch[x];
if(tr[q].len==tr[p].len+1)tr[now].fa=q;

例として、文字列 aaba に対して図示すると以下のようになります（贺による）。

さらに、不一致の場合を考えます。

なぜ上記の方法を使えないのか？例えば上記の図に b を追加した場合、\(p=2,q=4\) が見つかり、\(len_q=3,len_p=1\) となり、\(q\) の \(\text{endpos}\) に \(n\) が含まれないことが分かります。

そこで、新しいノードを作成し、親ノードを設定します。これにより、既存の文字列に含まれない接尾辞を表します。上図では ab に相当し、\(len\) は \(len_q+1\) となります。\(q\) の親も新しいノードに変更され、元々一致しなかった \(q\) が \(p\) で一致できるようになります。

最後に、元の \(ch[c]\) が \(q\) を指すノードをすべて新しいノードに変更します。

最終的なコードは以下の通りです：

void add(int x){
    int p=las,now=las=++tot;tr[now].len=tr[p].len+1;siz[tot]=1;
    for(;p&&!tr[p].ch[x];p=tr[p].fa)tr[p].ch[x]=now;
    if(!p)tr[now].fa=1;
    else {
        int q=tr[p].ch[x];
        if(tr[q].len==tr[p].len+1)tr[now].fa=q;
        else{
            int t=++tot;tr[t]=tr[q];
            tr[t].len=tr[p].len+1;
            tr[now].fa=tr[q].fa=t;
            for(;p&&tr[p].ch[x]==q;p=tr[p].fa)tr[p].ch[x]=t;
        }
    }
}

aabab の図は以下の通りです：

以上でSuffix Automatonの構築が完了しました。次に簡単な応用例を紹介します。

P3804

小文字アルファベットのみからなる文字列 \(S\) が与えられる。

出現回数が1ではない部分文字列の出現回数 × 長さ の最大値を求めよ。

\(|S|\le 10^6\)。

Suffix Automatonを構築し、各等価クラスの答えは集合のサイズ × \(len\) で求められます。集合のサイズは部分木のサイズを求めるような方法で加算可能です。

コード例