文字列アルゴリズム

概要

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は対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(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では扱わないもの

  • なし

根拠