AIで解説 AtCoder攻略　Suffix Array・Trie・Hash

Suffix Array・Trie・Hashページの位置づけ

項目	内容
必修度	標準
学習目安	発展
前提	文字列・配列
対象問題	18問（推定値あり18問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	2
標準	0〜799	4
標準〜発展	800〜1199	2
発展	1200以上	10
未算出	—	0

接尾辞配列・ハッシュ・Trie・編集距離を使って、長い文字列や大量の部分文字列をまとめて比較します。単純な文字列走査とは前処理と問い合わせの計算量で使い分けます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

Suffix Array・Trie・Hashの見分け方

部分文字列の比較を大量に行う
接頭辞・接尾辞の共通部分を使う
1文字の挿入・削除・置換を距離として扱う

Suffix Array・Trie・Hashの実装前チェック

前処理の計算量とメモリを見積もる
ハッシュ衝突や法の選択を確認する
添字の半開区間を統一する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC347 B Substring（公式解説）を解きます。全ての部分文字列を切り出してsetへ入れます。setが重複を自動で消すので、異なる部分文字列の個数をそのまま数えられます。

S = input().strip()
substrings = set()
for left in range(len(S)):
    for right in range(left + 1, len(S) + 1):
        substrings.add(S[left:right])
print(len(substrings))

部分文字列はO(N^2)個あり、コピーを含めるとO(N^3)程度です。Nが小さい制約で使える全探索です。

Suffix Array・Trie・Hashの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC347 B Substring	公式解説	Official editorial intent is classified as distinct substring set.	-238
ABC428 B Most Frequent Substrings	公式解説	公式Editorialの方針を frequent substring count として整理する。	-89
ABC386 C Operate 1	公式解説	挿入・削除・置換のいずれか一回以内で一致するかを二ポインタで判定する。	218
ABC372 C Count ABC Again	公式解説	更新位置の前後だけを再計算し、文字列中のABC出現数をオンラインで保つ。	336
ABC324 C Error Correction	公式解説	Check whether each string differs from the target by at most one insertion, deletion or replacement.	637

次に解く

問題	公式解説	出題意図	difficulty
ABC287 D G. Match or Not	公式解説	?をワイルドカードとして、各分割位置の前後文字列が一致するか差分配列で判定する。	796
ABC398 F I. ABCBA	公式解説	Find the longest palindromic suffix with linear-time string matching, then append the reverse of the remaining prefix.	1033
ABC287 E H. Karuta	公式解説	文字列を辞書順に並べ、隣接文字列との最長共通接頭辞を比較して各値を求める。	1093
ABC353 E H. Yet Another Sigma Problem	公式解説	Official editorial intent is classified as trie prefix group sum.	1217
ABC403 E H. Forbidden Prefix	公式解説	公式Editorialの方針を trie prefix query として整理する。	1447

挑戦問題

問題	公式解説	出題意図	difficulty
ABC367 F I. Rearrange Query	公式解説	Official editorial intent is classified as multiset range hash query.	1540
ABC331 F I. Palindrome Query	公式解説	Use double rolling hashes to compare a string with its reversed substrings.	1666
ABC339 F I. Product Equality	公式解説	Official editorial intent is classified as product equality hash count.	1716
ABC458 F Critical Misread	公式解説	Model critical misreads as automaton states and count valid strings.	1744
ABC386 F I. Operate K	公式解説	編集距離の幅K以下だけを帯状DPで計算し、長大文字列を線形近くで判定する。	1875