コンテンツにスキップ

Suffix Automaton

タグ「Suffix Automaton」の記事 2 件

Suffix Automaton のリンク集

Suffix Automaton について、参考になる記事や資料をまとめました。

Suffix Automaton は、文字列 SS のすべての部分文字列を受理する最小の DFA(決定性有限オートマトン)です(終端状態を SS の suffix に限ると、suffix だけを受理する最小の DFA になります)。各状態は、SS の中での出現位置の終端の集合(endpos)が等しい部分文字列の集まりを表します。∣S∣=N≥2|S| = N \ge 2 のとき状態数は 2N−12N - 1 以下、N≥3N \ge 3 のとき遷移数は 3N−43N - 4 以下で、1 文字ずつ末尾に追加するオンラインのアルゴリズムで線形時間で構築できます。各状態から「その状態に入らない最長の suffix」の状態へ張る suffix link は木になり、この木は逆文字列 rev(S)\mathrm{rev}(S) の suffix tree と同じ形です。

遷移を長さ σ\sigma(文字の種類数)の配列で持つと速いですが、メモリは O(Nσ)O(N\sigma) です。英小文字で N=5×105N = 5 \times 10^5 なら、状態が最大 10610^6 個なので、int の配列で 100 MB ほどになります。map などで持つとメモリは O(N)O(N) ですが、構築が O(Nlog⁡σ)O(N \log \sigma) になり、定数倍も重くなります。定番の使い方には、異なる部分文字列の個数(len(link(v))\mathrm{len}(\mathrm{link}(v)) を suffix link の先の状態の最長の長さとして、初期状態以外の各状態 vv について len(v)−len(link(v))\mathrm{len}(v) - \mathrm{len}(\mathrm{link}(v)) を足す。答えは 64 bit 整数が必要)、ある文字列の出現回数(suffix link の木の部分木で endpos の大きさを数える)、2 つの文字列の最長共通部分文字列(片方の Suffix Automaton の上でもう片方を読み、遷移できないときは suffix link をたどる)などがあります。

  • Suffix Automaton(よすぽの日記)
    • Suffix Automaton を rev(S)\mathrm{rev}(S) の圧縮した Suffix Tree から作れることを図で示し、頂点数・辺数の上限の証明、構築アルゴリズム(clone の判定に len\mathrm{len} を使う)、構築の計算量、異なる部分文字列の個数などの応用を短く説明しています。最後に C++ の実装があります。下の ABC433 G の公式解説でも紹介されています。
    • 「性質」と「問題例」の節で「部分列」と書いているところは「部分文字列」の意味です。また、実装は last を戻して複数の文字列を追加する使い方には対応していません(下の「複数の文字列」の節を参照)。
  • Suffix Automaton(cp-algorithms、英語)
    • endpos と suffix link の定義から、構築アルゴリズム、その正当性と計算量、状態数 2n−12n - 1・遷移数 3n−43n - 4 の証明までを順に説明しています。後半の応用の節は、異なる部分文字列の個数、辞書順 kk 番目の部分文字列、出現回数、最初の出現位置、2 つや複数の文字列の最長共通部分文字列など 11 個あります。e-maxx.ru のロシア語の記事の翻訳です。
    • コードは C++ で、遷移を map<char, int> で持ち、状態をグローバルな配列に入れる書き方です。遷移を配列で持つ場合のメモリと速度の違いにも触れています。

構築は、末尾に文字 cc を追加するたびに、直前の文字列全体の状態から suffix link をたどって cc の遷移を張り、必要なら状態を分割(clone)する、という手順です。

  • Suffix Automatonでもやもやした部分をなんか書いただけ(迷いませんか?)
    • cp-algorithms の構築の手順について、「なぜ suffix link をさかのぼりながら遷移を張ってよいのか」「なぜ clone が必要なのか」などの疑問に答える形で補足しています。S=abcbccS = \texttt{abcbcc} に 1 文字ずつ追加していく図があります。
    • 筆者自身が「多分」と書いている箇所もあり、cp-algorithms と合わせて読む補足として使うのがよいです。
  • A short guide to suffix automata(quasisphere、Codeforces、英語)
    • 「部分文字列を 1 文字ずつ聞かされて、出現しうる位置の集合だけを覚えておく」というゲームから状態の意味を導き、suffix link、構築、C++ の実装、簡単な応用を短く説明しています。suffix link の木が逆文字列の suffix tree になることにも触れています。
    • 「異なる部分文字列の個数は経路の個数」とあるのは、空の経路を含むので、実際の個数は 11 を引いたものです。

複数の文字列のすべての部分文字列を受理するオートマトン(一般化 Suffix Automaton)は、1 つの Suffix Automaton に「last を初期状態に戻してから次の文字列を追加する」ことを繰り返して作ることもあります。ただし、そのままだと追加したい文字の遷移がすでにある場合に無駄な状態ができるので、その場合を別に扱う必要があります。

  • 广义后缀自动机(OI Wiki、中国語)
    • 複数の文字列から Trie を作り、BFS の順に Suffix Automaton の構築を行う方法を説明しています。区切り文字で連結する方法や last を戻す方法(「伪广义后缀自动机」)の問題点、すべての文字列の異なる部分文字列の個数や複数の文字列の最長共通部分文字列への応用も扱っています。C++ のコードは遷移を配列で持っています。
  • 下の USACO Guide の例題「Standing Out from the Herd」の解答コードは、last を戻して追加する方法で、すでに遷移がある場合も正しく扱っています。

suffix link の木は rev(S)\mathrm{rev}(S) の suffix tree なので、rev(S)\mathrm{rev}(S) の Suffix Automaton を作れば SS の suffix tree が得られ、さらにその DFS 順から SS の Suffix Array が得られます。Suffix Array と LCP 配列で解ける問題の多くは Suffix Automaton でも解けるので、どちらで解くかは好みや問題によります。

  • String Suffix Structures(USACO Guide、英語)
    • Suffix Automaton、Suffix Tree、Suffix Array を相互に変換する方法(suffix tree の DFS から Suffix Array を作る、Suffix Array と LCP 配列から suffix tree を作る、Suffix Automaton の suffix link から suffix tree を作る)を C++ のコード断片で紹介し、例題を一般化 Suffix Automaton で解いています。どの構造でも解ける問題の一覧があります。解説は短く、詳しくは cp-algorithms などへのリンクに任せています。
    • suffix tree を扱う 2 つのコード断片は、ループ変数がグローバルな配列と同じ名前(c や l)になっていて、そのままではコンパイルできません。

Suffix Automaton を扱う講座はまだありません。文字列の分類にある講座は、今のところ「文字列の並べ替えと辞書順最小化」だけです。

  • string/suffix_automaton.hpp(maspy’s library)
    • C++ の実装で、遷移を長さ sigma(既定は 26)の配列で持ちます。構築後に状態を len\mathrm{len} の昇順(トポロジカル順)に並べ替え、各状態の出現回数と出現位置の最小・最大も求めます。suffix link の木を作る関数、SS の区間 [L,R)[L, R) に対応する状態を求める関数、もう 1 つの文字列を読みながら最長一致を追う next もあります。ドキュメントはなく、説明はコード中のコメントだけです。

百科事典・英語・中国語の資料

Section titled “百科事典・英語・中国語の資料”
  • Suffix automaton(英語版 Wikipedia)
    • 歴史、right context(右側の文脈)と endpos による状態の定義、suffix tree との関係、状態数と遷移数の上限(それぞれ abn−1ab^{n-1} と abn−2cab^{n-2}c で達成されること)、擬似コードつきの構築、CDAWG・複数の文字列・スライディングウィンドウへの一般化、応用までを網羅しています。
    • 日本語版の「接尾辞オートマトン」は数行の短い記事で、図も suffix だけを受理する非決定性のオートマトンなので、競プロの Suffix Automaton を知るには向きません。
  • 后缀自动机 (SAM)(OI Wiki、中国語)
    • cp-algorithms と同じ e-maxx.ru の記事の翻訳がもとで、内容もほぼ同じです(構築、正当性、状態数と遷移数、11 個の応用)。図が多く、最後に練習問題の一覧があります。
  • Library Checker - Number of Substrings:異なる部分文字列の個数を求めます。N≤5×105N \le 5 \times 10^5 で、ライブラリの verify 用です。
  • CSES - Distinct Substrings:上と同じく異なる部分文字列の個数を求めます。n≤105n \le 10^5 です。
  • CSES - Substring Distribution:長さごとに異なる部分文字列の個数を求めます。各状態が受け持つ長さの区間に、いもす法で 11 を足します。
  • CSES - Counting Patterns:各パターンの出現回数を求めます。suffix link の木で各状態の endpos の大きさを数えておきます。
  • SPOJ - LCS(Longest Common Substring):長さ 250000250000 以下の 2 つの文字列の最長共通部分文字列の長さを求めます。
  • SPOJ - SUBLEX(Lexicographical Substring Search):異なる部分文字列のうち辞書順で KK 番目のものを答えるクエリに答えます。各状態から出る経路の個数を数えておきます。
  • ABC433 G - Substring Game:Suffix Automaton の上でコマを動かすゲームに言い換え、後退解析で勝敗を求めます(公式解説)。
  • Codeforces 235C - Cyclical Quest:xix_i の巡回シフトのどれかと一致する ss の部分文字列の個数を求めます。xixix_i x_i を ss の Suffix Automaton の上で読み、同じ状態を重複して数えないようにします。
  • 競プロキャンプ2026関西 J - Substring Query
    • SS の Suffix Automaton の上で各クエリの文字列 TT を前から読み、遷移できないときは suffix link をたどって、SS と TT の最長共通部分文字列の長さを求めています。

競プロキャンプ2026関西 J - Substring Query

英小文字からなる文字列 SS が与えられます。QQ 個のクエリで文字列 TiT_i が与えられるので、SS と TiT_i の両方の部分文字列である空でない文字列のうち、最長のものの長さを答える問題です(なければ 00)。制約は 1≤∣S∣≤20001 \le |S| \le 2000、1≤Q≤2×1051 \le Q \le 2 \times 10^5、∑∣Ti∣≤106\sum |T_i| \le 10^6 です。

TT の各位置 jj について、TT の jj 文字目で終わる文字列のうち SS の部分文字列であるものの最長の長さを ℓj\ell_j とします。共通の部分文字列はどれも TT のどこかの位置で終わるので、答えは ℓj\ell_j の最大値です。

ℓj\ell_j は、SS の Suffix Automaton を使うと、TT を前から 1 文字ずつ読みながら求められます。Suffix Automaton は SS のすべての部分文字列を受理するオートマトンです。各状態は SS の部分文字列の集まりを表し、状態の数は O(∣S∣)O(|S|) です。

TT の jj 文字目までを読んだとき、長さ ℓj\ell_j の文字列(その位置で終わる、SS の部分文字列である最長の文字列)を表す状態 vv と ℓj\ell_j を持っておきます。次の文字 cc を読むときは、次のようにします。

  • vv から cc で遷移できれば、遷移して長さを 11 増やす。
  • 遷移できなければ、先頭の文字を削って短くする。Suffix Automaton では、これは suffix link をたどることにあたる。遷移できるようになるか初期状態に戻るまでたどってから、遷移を試す。

長さは 1 文字読むごとに高々 11 しか増えないので、suffix link をたどる回数の合計は ∣T∣|T| 以下です。よって、1 つのクエリは O(∣T∣)O(|T|) で処理でき、全体の計算量は O(∣S∣+∑∣Ti∣)O(|S| + \sum |T_i|) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/suffix-automaton.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(Q);
STR(S);
SuffixAutomaton sam(S);
rep(Q) {
STR(T);
print(max(sam.match_lengths(T)));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SuffixAutomaton は Suffix Automaton で、既定では英小文字を扱います。match_lengths(T) は上の ℓj\ell_j を TT の各位置について並べた列を返すので、その最大値を出力しています。

使用ライブラリ:cpp_include@c3d3c0f