Rolling fingerprintで列の同値性を比較する

概要

列の順序と長さを保つrolling fingerprintを作り、連結・部分列の切り出し・回文比較へ使う。集合や代数式の乱択fingerprintは乱択アルゴリズムの単元で扱う。

考え方

文字列を多項式評価へ写し、prefix hashとbaseの冪からsubstringの指紋をO(1)で求める。等しい列は同じ値になり、異なる列にも衝突の可能性が残る。

具体的な初期化・切り出し・連結・LCP二分探索は列・文字列のrolling fingerprintで導出する。そこで使う保証は、文字の単射な符号化から得る非零多項式と、ランダムな評価点の根の個数に基づく。多重集合・指数vector・巨大整数式には別の構成と衝突評価が必要であり、この構造単元では順序を持つ列の比較へ進む。

成立条件と計算量

前処理O(N)、substring hash O(1)。比較する長さを揃え、modの正規化と乗算overflowを扱う。ランダムbaseの誤り評価には体・次数・選択集合の条件が必要。厳密な一致が要るならsuffix索引などを選ぶ。

下位単元

問題一覧

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

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

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。列の一致判定を連結可能な要約へ写し、衝突のある比較として扱う入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-string-hash

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 全接尾辞の辞書順索引と回文半径。

根拠