STEP 3.1A (別解)

<問題> 対象の文字列(テキスト)中に、探したい文字列(パターン)が含まれているかどうかを調べよう。(力ずくのアルゴリズムをプログラムしよう)(pp.97-102)

<実行結果> 
探したい文字列を入力してください :ababc
t[0] = a
t[1] = b
t[2] = a
t[3] = b
t[4] = d
t[5] = a
t[6] = b
t[7] = a
t[8] = b
t[9] = c
t[10] = c
t[11] = b
t[12] = d
t[13] = c
t[14] = a
t[15] = b
t[16] = c
t[17] = a
t[18] = d
t[19] = b
cnt = 16 (← 比較回数をカウントする変数cntを追加、比較回数を表示。p100 図5.3 )
Pattern ababc is matched at 5

探したい文字列を入力してください :tsuchiya
t[0] = a
t[1] = b
t[2] = a
t[3] = b
t[4] = d
t[5] = a
t[6] = b
t[7] = a
t[8] = b
t[9] = c
t[10] = c
t[11] = b
t[12] = d
t[13] = c
t[14] = a
t[15] = b
t[16] = c
t[17] = a
t[18] = d
t[19] = b
cmp = 20 (←tと各文字の比較。20回)
Pattern tsuchiya is not found

(p102 最下部: 下例のように、パタンがかなりマッチしたあとに失敗/再比較を繰り返すようなひどい処理はあまりおきない。この例も20回程度の比較である)


解答例

#include <stdio.h>
#include <string.h> /* 文字関係のライブラリ よくわかるC p71 */

/* プロトタイプ宣言 */
void print_text(char []); /* 文字列配列tの表示 */
int naive(char [], char []); /* 引数は文字の配列。別の書き方もある */


int main (void) {
    char t[30]; /* 最後は \0 ヌル文字なので、最大29文字 */
    char p[10];
    int j; /* 戻り値をうけとる変数 マッチするならt上の添え字 */

    /* テキストは、教科書の例 p98 */
    strcpy(t, "ababdababccbdcabcadb"); /* 文字列の代入 よくわかるC p68 */

    /* パターンは入力 p98 */
    printf("探したい文字列を入力してください :");
    scanf("%s", p);
 
    print_text(t);    /* テキストの出力 */
    j = naive(t,p);   /* 素朴、力づく、力まかせのアルゴリズム実装 */
 
    /* 戻り値に応じて、出力文 */
    if (j == -1) /* 見つからない */
        printf("Pattern %s is not found \n", p);
    else /* テキスト配列tの添え字jから見つかった */
        printf("Pattern %s is matched at %d \n", p,j);

    return 0;
}

int naive (char t[], char p[]){
    int i = 0;
    int j = 0;
    int m = strlen(p); /* 文字列 pの長さ */ 
    int n = strlen(t); /* 文字列 tの長さ */

    int cmp=0; /* 比較カウント用 */

    while (j < n) {                /* jの位置。tの配列要素がある間  j < m-nとすると、もっとすっきり書ける */
        i = 0;
        while (j+i < n) {          /* 比較位置。tの配列要素がある間 */
            cmp++;
            if (t[j+i] == p[i] ) { /* 比較する文字が一致したら (pはNULLまで進むので、この条件はやがて必ず失敗する) */
                i++;               /* 次の文字へ */
                continue;          /* 照合を継続 */
            } else {
                break;            /* jの位置からの照合は終了 */
            }
        }
        if (i == m) {               /* m個が一致ということなら */
             printf("cmp = %d \n", cmp);  /* pのNULLも比較していることに注意。STEP3.1Aの出力よりも1つ多い */
             return j;            /* 照合開始位置jをreturn */
        } else
             j++;                 /* jを1つ進めて、繰り返し */
    }

    printf("cmp = %d \n", cmp); /* 
    return (-1);

}


void print_text(char t[]) {
    int j = 0;
    while (t[j] != '\0') {  /* 最後のヌル文字ではない */
        printf("t[%d] = %c\n", j, t[j]); /* 1文字をプリント */
        j++;
    }
}