よくどれがどれかわからなくなるので
■suffix_array
◆概要
長さnの文字列sのSuffix Arrayとして、長さnのvectorを返す。
◆例
string s = "missisippi";に対して
{9,6,4,1,0,8,7,5,3,2}を返す
{
"i",
"ippi",
"isippi",
"issisippi",
"missisippi",
"pi",
"ppi",
"sippi",
"sisippi",
"ssisippi",
};
Suffixの辞書順と対応する
■lcp_array
◆概要
長さ n の文字列 s のLCP Arrayとして、長さ n-1 の配列を返す
◆例
bananaのSuffix Arrayは{5,3,1,0,4,2}であり
Suffixをソートしたものは{"a","ana","anana","banana","na","nana"}である
隣接に要素のlcpは{1,3,0,0,2}
■z_algorithm
◆概要
入力の長さを n として、長さ n の配列を返す。
i 番目の要素は s[0..n)とs[i..n)のLCP(Longest Common Prefix)の長さ。
◆例
abcababcに対して
{8,0,0,2,0,3,0,0}を返す
■KMP法(MP法)(解説動画からライブラリ拝借)
◆概要
文字列Sの長さを n として、長さ n + 1 の配列を構築する
f(i+1) := S[0,x] = S[i-x,i]となる最大のx(i-x>0)
findAll()で文字列sから文字列tを探すこともできる
◆例
abacababに対して
{-1,0,0,1,0,1,2,3,2}を返す
