文字列検索系

ローリングハッシュ

• 中身についてはハッシュ に記載されているローリングハッシュを参照
• できること
  • 2つの部分文字列の一致判定
  • LCP を求める
    • ロリハ + 二分探索で求める
  • セグ木に乗せて、文字列変更 & 文字列一致判定
    • ABC331 F - Palindrome Query
      • 1点変更 & 区間回文判定
      • ロリハはモノイドを成すのでセグ木と相性がいい

LCP（Longest Common Prefix)

• LCP の求め方
  • 2つの文字列のLCP
    • 愚直に計算すれば良い
  • 2つの部分文字列のLCP
    • 前処理としてロリハを O(n) で計算
    • クエリごとにロリハ + 二分探索で O(log n) で求められる
  • 複数文字列があるとき、ある2つの文字列のLCPを高速に求める方法
    • 前処理としてソートして、隣り合った2つのLCPを求めておく。
    • クエリごとに range min をする
  • Suffix の LCP
    • LCP Array (後述)
• LCP でできること
  • 辞書順比較: 、LCP の次の文字の大小関係を見ればよい
    • https://qiita.com/NokonoKotlin/items/b58b9f81b26b2fff2a65

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 が部分文字列として現れる位置が二分探索で求められる。
    • 計算量
      • 構築: $O(|T|)$
      • クエリ: $O(|P| \log |T|)$
    • 部分文字列は Suffix の Prefix である。つまり、Suffix Array で二分探索をすればよい。(Suffix Array のうち P が Prefix として現れるものが区間として現れる）
    • 出題例: ABC 362 G - Count Substring Query
      • sの部分文字列にtはいくつあるかを求める
    • 実装例
    • P が現れる最左位置であっても range min で求められる
  • 複数の文字列(T_i)が与えられたとき、文字列 P が現れる i が求められる
    • (T_i)を\0など連結して Suffix Array を構築すれば良い
    • 最小のiであっても二分探索でSAの範囲を求めてrange min すれば良い

(参考: 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 の長さ

• 例

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

• できること

  • 2つの部分文字列のLCP
    • range min query でできるはず
  • 2つの部分文字列の辞書式順序比較
    • 2つの部分文字列の LCP を求めて次の文字を比較する
  • 最長重複部分文字列
    • LCP Array の最大値
  • 部分文字列の数
    • $n(n+1)/2$ から LCP Arrray の総和を引いたもの
  • LCS (2つの文字列の最長共通部分文字列)
    • S+T に対して LCP Array を求める。
  • 辞書順で K 番目の部分文字列
    • LCP の累積和を考えるとできるらしい
  • 文字列マッチングの高速化
    • SA では $O(|P| \log |T|)$ だったのが LCP Array を使うと $O(|P| + \log |T|)$ でできるらしい
    • 文字列マッチングのためのLCP Arrayを構築する - $shibayu36->blog;

• 問題例

  • AtCoder Library Practice Contest I - Number of Substrings
    • 重複分は最小添字のみ数える。
      • 同値類の数え上げとして考えたとき代表元として、最小添字のものを考える
    • 画像

Z Algorithm

• アルゴリズムの概要

  s と s の各 suffix の LCP の長さを求める