文字列における高速パターンマッチング

与えられた1つの文字列内でのすべての出現を見つけるアルゴリズムを提示します。その実行時間は、文字列の長さの合計に比例します。比例定数は実用的な利用が可能なほど低く、この手法はより一般的なパターンマッチング問題にも対応できるように拡張できます。このアルゴリズムの理論的応用では、偶数の回文の連結の集合、すなわち言語 \ R\^* は線形時間で認識できることが示されます。平均してさらに速く動作する他のアルゴリズムも考慮されています。