文字列

文字列に関するアルゴリズム、典型問題、実装テクニックをまとめる。

アルゴリズム

名前	何ができるか	計算量
Z-Algorithm	各位置からの共通接頭辞長を求める	O(N)
Manacher	各位置を中心とする回文半径を求める	O(N)
Rolling Hash	任意の部分文字列の高速比較	構築 O(N)、比較 O(1)

典型問題

名前	内容
LCS	2つの文字列の最長共通部分列
回文	回文判定・最長回文
suffix最長回文	文字列の末尾にある最長回文