<問題> 対象の文字列(テキスト)中に、探したい文字列(パターン)が含まれているかどうかを調べよう。(力ずくのアルゴリズムをプログラムしよう)(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
解答例 #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++; } }