力まかせ探索
力まかせ探索 (Broute Force Search) は探索アルゴリズムの一種です。探索対象文字列の中から特定の文字列を探し出します。
文字通り、単純かつ力任せのアルゴリズムです。単純に探索対象文字列の先頭文字から順に、特定の文字列に一致するか確認します。
探索対象文字列の文字数を N , 探索する文字列(パターン)の文字数を M とすると、最悪計算量は O(MN) です。これは探索対象文字列のループの中で、探索する文字列(パターン)をループするためです。ですが実用上、パターンの文字列すべてを確認するまでもなく、先頭数文字でマッチしないことが多くなるので、だいたい O(N) で済むようです。
アルゴリズムの解説
- i=0 から 探索対象文字列数までループします。
- j=0 からパターン文字数分ループします。
- パターン j 文字目 と 探索対象文字列 i+j 文字目を比較し、一致しなければ 2. のループを抜けます。
- パターン文字列末尾まで一致した場合、i がパータン文字列の開始位置になります。
- 1. のループで見つからない場合、探索文字列の中にパターンは存在しません。
ABCの3文字から構成される文字列 "AABABBABABCAB" から "ABABCA" というパターンの文字列を探す場合、具体的には以下の表のように探索することになります。探索開始位置が1文字ずつずれているのが確認できます。
| A | A | B | A | B | B | A | B | A | B | C | A | B | |
| 1 | A | B | |||||||||||
| 2 | A | B | A | B | C | ||||||||
| 3 | A | ||||||||||||
| 4 | A | B | A | ||||||||||
| 5 | A | B | |||||||||||
| 6 | A | ||||||||||||
| 7 | A | B | A | B | C | A |
先頭文字からから順に目的のパターン文字列が見つかるまで次の文字に進みながら探索します。表を見てわかるのは、探索対象文字列の同じ位置の文字を何度も確認しているということです。
例えば2文字目からの探索では、6文字目まで進んで確認しているのに、3文字目からの確認の際に後ろ(3文字目)に戻ってしまいます。この点は改良の余地があります。
サンプルコード
C#
public static int BrouteForceSearch(string target, string pattern)
{
// 探索対象文字列の先頭から走査
for (int i = 0; i < target.Length; i++)
{
// マッチするか確認
for (int j = 0; j < pattern.Length; j++)
{
// マッチしない場合は抜ける
if (pattern[j] != target[i + j]) break;
// すべてにマッチした
if (j == pattern.Length - 1) return i;
}
}
// 最後までマッチしなかった
return -1;
}