Brute force algorithm 力任せな文字列照合アルゴリズム

文字列照合を行うための最も自明（素朴）な方法は、テキスト内のパタンが存在する可能性のある全ての位置を順番にチェックするものです。テキストの位置 i が 0 から n - m について、T[i + j] = P[j] ( 0 ≦ j ≦ m - 1 ) を満たすかをチェックします。

T[i] ≠ P[j] が検出されたときに、i = i - j + 1 (次の i の位置) j = 0 (パタンの先頭)にリセットします。（下図参照） 文字列照合アルゴリズムでは、文字を比較する回数により計算効率を評価します。Brute force algorithm は最悪の場合 m( n - m + 1) 回の比較が必要なので、m が n に比べて十分小さいと考えるとオーダーは O(nm) となります。例えば、テキスト "000000001" に対して、パタン "001" の照合がこの最悪のケースを引き起こします（試してみましょう）。 しかし、実際のテキストエディタなどのアプリケーションで、この最悪のケースが発生することはないと考えて良いでしょう。なぜなら、T[i + j] と P[j] をチェックする内側のループは高確率で j = 0 のときに終了することが考えられるからです。従って、文字コードが多い実際の文字列に対しては、Brute force algorithm で十分実用的なのです。 しかし一方で、先ほどの例のように、バイナリ（S = {0, 1}）のテキストなど、ある特定の文字列に対しては非常に効率が悪くなります。

Brute force algorithm の流れ

int bruteForceSearch( string T, int n, string P, int m ){
    int i, j;
    i = j = 0;
    while ( i <= n - m ){
        while( i < n && j < m ){
            if ( T[i] != P[j] ){
                i = i - j + 1; j = 0;
            } else { i++; j++; }
        }
        if ( j == m ) {
            match( i - j );
            i = i - j + 1; j = 0;
        }
    }
}