検索する手法あれこれ。使うだけなら、1対1のString型の検索であれば、下手に自力実装するよりfind()など組み込み関数を使った方が一般的には高速となる。複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。Force)計算量$O(|S||T|)$概要まずは基本。文字目が一致するか照合していく。$O(|S|)$概要1対1の検索アルゴリズム。文字目で照合失敗したら次は何文字ずらすか」テーブルを作っておき、マッチ位置を試す位置を少なくする。そのマッチ位置では既に'AB'が一致しているので、2文字飛ばせる。文字目で失敗した場合、次の位置は以下のようにすればよい。文字目で失敗した際に次のマッチ位置を1つ進めるため。側の文字も進める必要がある。Pythonでの実装例1つ見つかったら終了ではなく一致箇所全てを求めるため、テーブルサイズを1つ長くし、最後まで一致した後に次に合わせるべき位置も計算している。法ボイヤー-ムーア文字列検索アルゴリズム概要1対1の検索アルゴリズム。後ろから照合することで一般的な文字列ではスキップできる期待値が大きくなり、高速となる。そのため実用上よく使われている。同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。suffix規則」「両方計算してスキップできる距離の大きい方」が存在する。不一致文字規則は実装は簡単だが、文字の種類が少ない場合に効果が少ない。