探したい文字列を入力してください :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
f[0] = -1
f[1] = 0
f[2] = 0
f[3] = 1
f[4] = 2
cmp = 12
Pattern ababc is matched at 5

探したい文字列を入力してください :aaaab
t[0] = a
t[1] = a
t[2] = a
t[3] = a
t[4] = a
t[5] = a
t[6] = a
t[7] = a
t[8] = a
t[9] = b
f[0] = -1
f[1] = 0
f[2] = 1
f[3] = 2
f[4] = 3
cmp = 15
Pattern aaaab is matched at 5

解答例

#include <stdio.h>
#include <string.h>

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

int main (void) {
    char t[30]; /* 最後は \0 ヌル文字なので、最大29文字 */
    char p[10]; /* パターンは9文字 */
    int j; /* 関数の戻り値。照合成功か判定 */

    /* テキストは、教科書の例 p98 */
    strcpy(t, "ababdababccbdcabcadb"); /* 文字列の代入 よくわかるC p68 */
    /*   よくない例 */
//   strcpy(t, "aaaaaaaaab");  /* pはaaaab。bで不一致のあと、あまり進めない */

    /* パターンは入力 p98 */
    printf("探したい文字列を入力してください :");
    scanf("%s", p);

    print_text(t);  /* テキストの出力 */
    j = kmp(t,p);   /* kmp法でいこう。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 kmp (char t[], char p[]){
    int i = 0;
    int j = 0;
    int f[10]; /* 失敗関数値の配列 */
    int m = strlen(p);
    int n = strlen(t);
    int cmp = 0; /* 比較回数カウント用 */

    compute_f(p, f); /* 配列アドレス渡しに注意 たとえばpは&p[0] のこと*/
    print_f(f, m);   /* 失敗関数の作成結果を出力 */

    while (i < m && j < n) { /* どちらかを満たさなくなったら、ループを出る */
        if (i == -1) { /* 頭から不一致の場合: tは次のjへ移動 pはi=0から比較 */
            i = i + 1;
            j = j + 1;
        } else if (p[i] == t[j]) { /* tとpが一致している。進める */
            i = i + 1;
            j = j + 1;
            cmp++;
        } else { /* 一致しない。tのjは戻さない。pのiを移動 iが小さくなるほどうれしい。-1 < f[i] < iのはず i=0のときは -1*/
            i = f[i];
            cmp++;
        }
    }

   /* 比較回数をカウントしない場合は、以下のようにすっきり
    while (i < m && j < n) {
        if (i == -1 || p[i] == t[j]) {
            i = i + 1;
            j = j + 1;
        } else {
            i = f[i];
        }
    }
    */

    printf("cmp = %d \n", cmp);

    if (i == m) /* すべて一致してループを抜けた場合 */
       return (j - i);
    else
       return (-1);

}

/* 失敗関数の値を、fに */
/* i-1まで一致しているとき、iで不一致。f[i]を求める */
void compute_f (char p[], int f[]) { /* p同士を比較していく */
    int j = 0;  /* jは戻らない */
    int i = -1;
    int m = strlen(p);
    f[0] = -1; /* i==0で不一致のときの特例。先頭から異なるときの値の設定 */

    while (j < m) {
       if (i==-1 || p[i] == p[j]) { /* i==-1の特例処理か、一致している場合 */
           i++;
           j++; /* 次へ進む */
           f[j] = i; /* 失敗関数の確定 */
       } else {
           i = f[i]; /* 一致しないならjを進めず、iを進めて、再度比較へ */
       }
    }

}


/* 文字列の最後には\0 ヌル記号。番兵とみることもできる */
void print_text(char t[]) {
    int j = 0;
    while (t[j] != '\0') {  /* 最後のヌル文字ではない */
        printf("t[%d] = %c\n", j, t[j]); /* 1文字をプリント */
        j++;
    }
}

/* 失敗関数のプリント  */
void print_f(int f[], int m) {
    int i = 0;
    while (i < m) {
        printf("f[%d] = %d\n", i, f[i]); /* i-1まで一致 iで不一致のとき、f[i] */
        i++;
    }
}

STEP 3.2