基本的な考え方 ／ 理論的には？

基本的な考え方

テキスト（探索対象文字列）と パターン（探索文字列）
・「テキスト」から「単語で指定されたパターン」を探すにあたり、「不一致となった位置」と「単語自身の情報から次に照合を試すべき位置」を決定することで検索を効率化する

前処理
・「パターンに含まれる各文字」について、「その文字で不一 致になった際パターンをどれだけずらせばよいか」を調べて表にしておく

探索を行う
・上記表をもとにパターンをずらしていく

計算量
・O(n)

---

理論的には？

力任せ法よりも高速なアルゴリズム
・テキストとパターンの照合において後戻りは発生しないため、力任せ法（Brute Force Search）よりも高速なアルゴリズムとなる

---

現実的には？

問題点
・テーブルを作成するための前処理が複雑
・アルゴリズムが複雑な分だけオーバーヘッドが大きくなってしまう

短い文字列の場合
・結果的に力任せ法の方が効率が良いケースもある