ei1333の日記

ぺこい

最長共通部分接頭辞（LCP）

文字列　むっっっっっっっっっっっっっっず

お正月なので暇です　研究？　知らない子ですね....

うううう

長さ {N} の文字列 {S} と長さ {M} の文字列 {T} が与えられます。 次の {Q} 個のクエリに答えてください。

  • {(a, b, c, d)}: {S[a, b)} と {T[c, d)} を辞書順比較した結果を出力する (小さい or 大きい or 等しい）

この問題は {S[a, )} と {T[c, )} の最長共通部分接頭辞の長さ（以下LCPと表記します）が求まればよいです。LCP+1 番目の文字を比較してどちらが大きいか比較することで判定できます（一方が範囲外のとき別途処理）。

この問題に限定しなくてもLCPを求めたいときはよくあるような気がします。ここではLCPのいろいろな求め方を紹介します。

ちからまかせ

がぜる

時間計算量 {O(Q\min(N,M))}

以下に相当する場合はたぶんこれ

  • 制約が非常に小さい

概要

それぞれのクエリにたいして、 {S[a,)} と {T[c, )} の {1} 文字目から順に一致しているところまでループを回します。

実装例

int lcp = 0;
while(a + lcp < S.size() and b + lcp < T.size() and S[a + lcp] == T[b + lcp]) ++lcp;

今書きました　バグっていたらごめんなさい

おまけ

そんなものはない

DP

がぜる

時間計算量 {O(NM+Q)}

以下に該当する場合はたぶんこれ

  • {N,M} が 5000 くらい、 {Q} が 10000000000000000000000 くらい

概要

動的計画法（DP）による解法です。 {dp[i][j]} を {S[i,)} と {T[j, )} の LCP と定義します。

{i, j} を🐮ろから回して更新することにします。更新の式は {S_i \neq T_j} のとき {dp[i][j]=0}、 {S_i = T_j} のとき {dp[i][j]=dp[i+1][j+1] + 1} です。各クエリでは {dp[a][c]} の値を見れば良いです。

実装例

vector< vector< int > > dp(N + 1, vector< int >(M + 1));
for(int i = N - 1; i >= 0; i--) {
  for(int j = M - 1; j >= 0; j--) {
    if(S[i] == T[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
  }
}

今書きました　バグっていたらごめんなさい

おまけ

びーと

Z algorithm

がぜる

時間計算量 {O(N+M+Q)}

以下に該当する場合はたぶんこれ

  • {N,M} が {10^6} くらい、 {Q} が 10000000000000000000000 くらい、 {a} が {0} 固定

概要

長さ {N} の文字列 {S} が与えられたとき、各 {i (1 \leq i \leq N)} に対して {S} と {S[i,N]} の最長共通接頭辞（LCP）の長さ {A_i} を {O(N)} で求めるアルゴリズムです。

{S$T} を Z algorithm にかけます。すると {A_{N+1+c}} が {S} と {T[c,)} の LCP です。

実装例

ei1333.github.io

おまけ

一文字追加なら計算量は線形のままオンラインにできるらしいです。へのさんありがとう。

heno239.hatenablog.com

ろりは

がぜる

時間計算量 {O(N+M+Q \log \min(N,M))}

以下に該当する場合はたぶんこれ

  • {N, M, Q} が {10^6} くらい

定数倍が大きい（剰余演算する）ので注意が必要

概要

前計算として各 {i} について {S[0,i)} や {T[0,i)} をハッシュした値を求めておくと、任意区間のハッシュ値が {O(1)} で求まるねというアルゴリズムです。

{S[a,a+x) = T[c,c+x)} を満たす最大の {x} を求めればよく、 {x} について単調性があるため、ハッシュ値が一致するかどうかを見る二分探索が可能です。

実装例

ei1333.github.io

おまけ

{S} や {T} が変化するクエリ（文字の変更 or 連結 or 区間に対する変な操作）がある場合もローリングハッシュが有効です。（その区間のハッシュ値、その区間の文字数）はモノイドになっているため、これをセグ木や平衡二分木にのせられます。

ハッシュ値が衝突する可能性があり、嘘解法と揶揄される　衝突確率を見積もろう

SA

がぜる

時間計算量 {O(N+M+Q)} だが、どこかにlogがつくのが一般的

以下に該当する場合はたぶんこれ

  • {N, M, Q} が {10^6} くらい

概要

接尾辞配列（Suffix Array）とよばれるものがあり、う

SA-IS をすると接尾辞配列を線形時間で構築可能です。また、接尾辞配列からLCP Arrayと呼ばれるものを線形時間で構築できます。詳しくはぐぐってくだひゃい

{S$T} から接尾辞配列を求めたあと LCP Arrayを構築します。 {S[a, )} と {T[c, )} の LCP は、このLCP Arrayの対応する区間の最小値と一致することが言えるので、Sparse Table や Segment Tree などを用いて RMQ をします。

実装例

SA-IS　ほしいなあ　だれか　書いてね

おまけ

ほかのデータ構造（スタック、セグ木など）を併用すると、いろいろなクエリや数え上げに対応できます。 数え上げには強い気がします。

う～

　ええええ

次の問題を考えます。

長さ {N} の文字列 {S} と長さ {M} の文字列 {T} が与えられます。 {T} に含まれる {S} の個数を求めてください。

LCPが長さ {N} か判定（ロリハなら普通にハッシュ値の比較）しても良いですが、一致判定のみならば別のアルゴリズムも存在します。

KMP

がぜる

時間計算量 {O(N+M)}

以下に該当する場合はたぶんこれ

  • {N,M} が {10^6} くらい

概要

KMP の前計算では長さ {N + 1} の配列 {fail} を求めます。以下の性質を満たす有限オートマトンを構築するアルゴリズムのようにイメージするとわかりやすいかと思います。

  • 状態は {0, 1, \cdots, N} の {N + 1} つ
  • {0} が初期状態、 {N} が受理状態（その文字で終わる部分文字列が {S} と一致した状態）
  • 現状態が {k}、次の文字が {c} のとき、 {c \neq S_{k}} ならば {fail_{k}} に移動することを繰り返す。最後に、 {c = S_{k}} ならば状態 {k + 1} に移動する

明らかに、状態 {N} に訪れた回数が一致回数です。

おまけ

Z algorithmとほとんどおなじ

ワイルドカードマッチング

がぜる

時間計算量 {K=max(N,M)} として {O(K \log K)}

以下に該当する場合はたぶんこれ

  • {N,M} が {10^6} くらい
  • {S,T} の一部文字が ?（なんでもよい）

概要

展開します。

{c[i]d[i] ( a[i]^2 - 2 a[i] b[i] + b[i]^2)}

{= a[i]^2 c[i]d[i] - 2 a[i] b[i] c[i] d[i] + b[i]^2 c[i]d[i]}

{= (a[i]^2 c[i]) d[i] + (-2 a[i] c[i]) (b[i] d[i]) + c[i] (b[i]^2 d[i])}

3 つそれぞれ（一方をreverseして）畳み込んで、それらを足し合わせて {0} になるか判定すればよいです。

実装例

力尽きました

おおおお

うしどしです　うしー