文字列

Z-Algorithm

各$i$についてSとS[i..]の最長共通接頭辞をO(N)で求めるアルゴリズム

Knuth-Morris-Pratt法

まず文字列のBorder配列を求める

Border配列を愚直に求めると、$O(N^2)$の時間がかかってしまう

Boyer-Moore法

参考文献

文字列の辞典

Boyer–Moore string-search algorithm

On improving the worst case running time of the Boyer-Moore string matching algorithm