ローリングハッシュ

• 中身についてはハッシュ に記載されているローリングハッシュを参照
• 応用例
  • 部分文字列の辞書順比較
    • ロリハ+二分探索でLCP を求めて、LCP の次の文字の大小関係を見る。
    • https://qiita.com/NokonoKotlin/items/b58b9f81b26b2fff2a65
  • ABC331 F - Palindrome Query
    • 1点変更 & 区間回文判定
    • セグ木に乗っける

LCP（Longest Common Prefix)

• 2つの文字列のLCP
  • 愚直に計算すれば良い
• 2つの部分文字列のLCP
  • 前処理としてロリハを O(n) で計算
  • クエリごとにロリハ + 二分探索で O(log n) で求められる
• 複数文字列があるとき、ある2つの文字列のLCPを高速に求める方法
  • 前処理としてソートして、隣り合った2つのLCPを求めておく。
  • クエリごとに range min をする
• Suffix の LCP
  • LCP Array (後述)

Trie 木

tbw

↓がわかりやすそう。

トライ木(Trie木) の解説と実装【接頭辞(prefix) を利用したデータ構造】 | アルゴリズムロジック

Suffix Array

• アルゴリズムの概要

  長さ n の文字列 s が与えられたとき、以下の条件を満たす (0, 1,..., n - 1 ) の順列 sa を Suffix Array という。

  • s[sa[0]..] < s[sa[1]..] < ... < s[sa[n-1]..]

  要するに、n個ある suffix のソートができる。

  計算量はO(n) (愚直にやるとO(n^2 log n) なので、O(n) で計算できるのはかなりびっくり)

• 例

  • abracadabra による例
  • mississippi による例

• Suffix Array でできること

  • 文字列 T の中で、文字列 P が部分文字列として現れる位置が二分探索で求められる。
    • 部分文字列は Suffix の Prefix である。つまり、Suffix Array で二分探索をすればよい。(Suffix Array のうち P が Prefix として現れるものが区間として現れる）
    • 出題例: ABC 362 G - Count Substring Query
      • sの部分文字列にtはいくつあるかを求める

(参考: ACL string )

LCP Array

• アルゴリズムの概要

  長さ n の文字列 s が与えられたとき、以下の条件を満たす長さ n-1 の配列 clp_array を LCP Array という。

  • sa を s の Suffix Array としたとき clp_array[i] は s[sa[i]..] と s[sa[i+1]..] の LCP の長さ