文字列検索 の記事

文字列検索アルゴリズム入門 - KMP・Boyer-Moore・Rabin-Karpを動くコードで理解する

文字列検索アルゴリズムを動くPythonコードで解説します。素朴な全探索が最悪O(nm)に落ちる理由、Rabin-Karpのローリングハッシュと衝突検証、KMPのLPS配列がテキストのポインタを戻さない仕組み、Boyer-Mooreのbad character rule・good suffix ruleとHorspool版、Z配列の線形構築とパターン検索への応用、そして前処理と検索の計算量比較表まで整理し、CPythonのstr.findが使うCrochemore-Perrinのtwo-wayアルゴリズムやgrep・ripgrepの実装事情、複数パターンのAho-Corasickにも触れます。