文字列アルゴリズム
概要
Trieによる接頭辞共有とprefix matching・Z algorithmによる一致区間の再利用から、周期・回文を調べ、suffix arrayとLCPによる標準的な接尾辞索引へ進む。次に有限状態への同値化、pattern automaton、Aho–Corasick、subset construction、Suffix Automatonを続けて学ぶ。その後、runの局所変化と再帰的な圧縮文字列で、明示展開せずに列を扱う。rolling fingerprintはデータ構造章、automaton上の計数はDP章へ接続する。
文字列状態表現
一致・接辞・反復を十分な文字列状態へ圧縮する。
考え方
文字列は文字の列として走査する場合と、prefix・suffix・一致する区間の集合として扱う場合で必要な情報が変わる。まず比較を何回繰り返すのかを数え、一致長を再利用する索引か、将来の一致に必要な履歴をまとめる状態機械かを選ぶ。
成立条件と計算量
長さをN、文字種数をσとする。配列遷移と連想配列では時間・空間が変わるためσを隠さない。文字列を実際にコピーする費用も数える。章の目次から必要な表現を選び、各単元の直接前提を確認して問題へ進む。
章の構成
項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。
- Trieで共有接頭辞を索引化する — 水色
- 接頭辞との一致長を再利用する — 水色(導入)
- Z algorithmによるprefix matching — 水色。概念上の親: 接頭辞との一致長を再利用する
- 文字列周期・primitive word — 青色
- 回文半径と左右対称区間を特定する — 青色
- 接尾辞の順序とLCPを索引化する — 青色
- 禁止・要求patternを有限状態へ圧縮する — 青色(導入)
- 有限状態automatonの構成 — 青色。概念上の親: 禁止・要求patternを有限状態へ圧縮する
- Aho–Corasick — 黄色。概念上の親: 禁止・要求patternを有限状態へ圧縮する
- 非決定性automatonのsubset construction — 黄色。概念上の親: 禁止・要求patternを有限状態へ圧縮する
- Suffix Automatonで部分文字列集合を表す — 橙色
- run-length状態の動的遷移 — 青色
- 圧縮・反復・再帰文字列へ問い合わせる — 青色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC268 G「Random Student ID」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 法上の四則演算・高速累乗・逆元、Trieによる共有接頭辞の索引
- ABC343 G「Compress Strings」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: Z algorithmによるprefix matching(既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: Z algorithmによるprefix matching
- ABC403 E「Forbidden Prefix」 公式問題主題: 単調進行による償却解析
技能・出典
主題: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。既習技能: Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。)。主タグ: 単調進行による償却解析 / 補助タグ: Trieによる共有接頭辞の索引
- ABC434 F「Concat (2nd)」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: Z algorithmによるprefix matching(既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。)。主タグ: 貪欲法と交換論 / 補助タグ: Z algorithmによるprefix matching
前提・学習成果・出典
導入対象の目安: 水色(1200–1599)。prefix・suffix・一致長・有限状態という文字列の共有単位を学ぶ入口。
対象色の読み方は本書の読み方を参照してください。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-string
習得する技能
- 一致・接頭辞・接尾辞・反復に必要な文字列状態を特定できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
接頭辞・接尾辞・一致長などの文字列状態を共通言語にし、各種の照合・索引法へ進む土台を作る。
このUnitでは扱わないもの
- なし