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

    /* テキストも入力させるなら、上をやめて、下のように
    printf("文字列を入力してください :");
    scanf("%s", t);
    */

    /* パターンは入力 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); /* 文字列の長さ よくわかるC p71 文字列操作関数 */
    int n = strlen(t);

    /* 疑似コードを参考に 完成させてください。全体を、よく読み、納得すること*/
    /* printf 文を差し込むなどして、変数の状態を出力、確認してみるとよい */

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

    while (i < m && j < n) { /* p, t どちらかの照合部分が無くなるまでループ */
         cmp++; /* 下のif文が比較 */
         if (p[i] == t[j]) {  /* 一致している */
             i++; /* p, tともに、右へ1つ移動 *//
             j++;
         } else { /* 一致しない tのjをi分戻して、右へ1つ移動、比較へ */
             j = j - i + 1; /* +2では、tのjが右に1つ余計に移動 */
             i = 0; /* pのiは先頭に */
         }
    }
  
    printf("cmp = %d \n", cmp);
 
    if (i == m)
       return (j - i);
    else
       return (-1);

}

/* 文字列の最後には\0 ヌル記号。番兵とみることもできる */
/* strlenで文字列のサイズを得て、ループする方法もある */
/* よくわかるC言語 p65 は forループで。以下はwhileループ版 */
void print_text(char t[]) {
    int j = 0;
    while (t[j] != '\0') {  /* 最後のヌル文字ではない */
        printf("t[%d] = %c\n", j, t[j]); /* 1文字をプリント */
        j++;
    }
}

STEP 3.1A