Suffix Array の使い方
Suffix Array とは:
文字列に対して、各接尾辞を辞書順にソートしたもの。
接尾辞を開始インデックスで表して長さ$ Nの配列として表現する。
たとえば、helloの接尾辞はhello ello llo lo oとなるが、これを辞書順にソートするとello hello llo lo oとなる。
インデックスで表すと2 1 3 4 5となる。
Suffix Array の利用テクニック
(以下、Suffix Arrayを$ O(1)回のみ計算する場合、それに必要な計算量は省略する)
文字列$ Sから文字列$ Tが現れる位置をすべて取得したいとき:
これは$ SのSuffix Arrayと二分探索により実現できる。
まず、二分探索により$ Sの接尾辞のうち辞書順で$ T以上となる最小のものを見つける。これは$ O(|T| \log |S|)でできる。
つぎのSuffix Array上でこれより後ろとなる接尾辞のうち、$ Tを含まない最小のものを見つける。これも上と同じ計算量でできる。
$ O(|T| \log |T|)
code:rs
/// 文字列 s, t が与えられたとき、 s のうちに t が現れる位置をすべて返す。
fn find_substrings(s: &char, t: &char) -> Vec<usize> { fn unwrap_anyway<T>(x: Result<T, T>) -> T { match x { Ok(a) => a, Err(a) => a } }
fn is_prefix(s: &char, t: &char) -> bool { s.len() >= t.len() && s.iter().zip(t).all(|(&c, &d)| c == d ) } let sa = suffix_array(s);
let l = unwrap_anyway(sa.binary_search_by(|&i| &si .. >= t )); let r = unwrap_anyway(sal ...binary_search_by(|&i| !is_prefix(&si .., t) )); (l + l .. r).map(|j| saj ).collect::<Vec<_>>(); }
文字列$ Sと文字列$ TのLongest Common Substringを求めたいとき:
$ O(|T| \log |S| \log |T|)
code:rs
/// 文字列 s, t が与えられたとき、 s のうちに t が現れる位置をすべて返す。
fn find_lcs(s: &char, t: &char) -> Vec<usize> { fn unwrap_anyway<T>(x: Result<T, T>) -> T { match x { Ok(a) => a, Err(a) => a } }
fn is_prefix(s: &char, t: &char) -> bool { s.len() >= t.len() && s.iter().zip(t).all(|(&c, &d)| c == d ) } let sa = suffix_array(s);
let len = (0 ..= t.len()).collect::<Vec<_>>();
unwrap_anyway(len.binary_search_by(|&n| {
let l = unwrap_anyway(sa.binary_search_by(|&i| si .. >= tlen )); l < sa.len()
}))
}
TODO: LCP配列(Suffix Array上で隣り合うSuffixのLCP長)の利用についても書きたい
たぶんこれを読むのが一番早いと思います(参考にしていません)