「文字列」の記事

KMPの失敗関数：不一致のあと、パターンはどこへ戻るのか

KMP文字列探索で不一致のあとパターンのどの位置を次に比較するかを決めるf表とnext表の定義と作り方、探索全体が線形時間になる理由を、1977年の原論文とPrincetonの実装に沿って整理します。