ももの知恵の樹

C言語アルゴリズム-力まかせ探索

力まかせの探索 (brute force search)

力まかせの探索とは、文字列（テキスト）と探索文字列（パターン）を一文字ずつ比較する探索アルゴリズムです。テキストとパターンの文字を先頭から順番に比較し、パターンの末尾文字まで一致すれば探索は成功です。途中で文字が違っていれば探索は失敗です。


力まかせ探索の探索過程

テキストとパターンを順に比較していきます。

テキスト a c a b c c b
パターン比較1 a b c - - - -
パターン比較2 - a b c - - -
パターン比較3 - - a b c - -

力まかせ探索の性能

力まかせの探索アルゴリズムの計算量はO(mn)となります。

テキストの長さをn文字、パターンの長さをm文字とすると、パターンをテキストに合わせる位置は全部で「n - m + 1」通りあります。つまり、文字の比較は合計で「m(n - m + 1)」 回行われることになります。


C言語による力まかせの探索 (brute force search)のプログラム

ランダムに生成した文字列（a,b,cのみに限定）の中に「abc」のパターンが存在するかどうか探索します。 


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 16

/*!
 * @brief       配列にランダムな文字列を格納する。
 * @param[out]  array  格納先の配列
 * @param[in]   size   配列のサイズ
 */
static void
array_random_char(char *array, unsigned int size)
{
    int i;

    /* 起動毎に異なる乱数を発生させる */
    srand((unsigned int)time(NULL));
    for(i = 0; i < size; i++){
        array[i]= 'a' + (rand() % 3); /* 生成される文字はabcのいずれか */
    }
    array[size] = '\0';
}

/*!
 * @brief      文字列を探索する
 * @param[in]  text     検索対象文字列
 * @param[in]  pattern  検索文字列
 * @return     発見位置のポインタを返す。失敗したらNULLを返す。
 */
char *
brute_force_search(const char *text, const char *pattern)
{
    const char *p1 = text;
    const char *p2 = pattern;

    while(*p1 && *p2){
        if(*p1 == *p2){
            p1++;  /* テキストの位置を１文字進める */
            p2++;  /* パターンの位置を１文字進める */
        }else{
            p1 -= p2 - pattern - 1; /* 比較点から１つのみ進める */
            p2 = pattern;           /* パターンの位置を先頭にする */
        }
        printf("[compare]:(text=%s)(pat=%s)\n", p1, p2);
    }

    if(*p2 != '\0') return(NULL);
    return((char *)(p1 - (p2 -pattern)));
}

int
main(void)
{
    char text[DATA_SIZE + 1];
    char *pattern = "abc";

    /* ランダムな文字列で埋める */
    array_random_char(text, DATA_SIZE);

    printf("[text]   :%s\n", text);
    printf("[pattern]:%s\n", pattern);

    if(brute_force_search(text, pattern) == NULL){
        printf("[result] : not found\n");
    }else{
        printf("[result] : found\n");
    }
   
    return(EXIT_SUCCESS);
}


関連ページ