STEP 3.2

問題

実行例

[実行例] 
探したい文字列を入力してください :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


（プログラム中のテキストを変えて、再コンパイル。実行。
5+2+2+2+2+2で15回の比較。naiveと異なり、jが後戻りしないことに注意)

探したい文字列を入力してください :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

コメント

  • jは後戻りしない。
  • Pのi番目で失敗した場合、どの添え字から再照合するかを与える失敗関数を事前計算
  • 疑似コードは配列の添え字の先頭が1. Cは0
  • このアルゴリズムの計算量を考えよう。（O記法で表現する）
  • nをテキストの長さ、mをパターンの長さとして、考えよう。
  • 処理対象のmとnが大きくなると、このアルゴリズムの計算時間（最悪の場合）はどのように増加するかを分析しよう。
  • 最悪な場合とは、どんなPとTの場合だろうか。

解答例

[解答例（未完）]

例題集 


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

/* プロトタイプ宣言 */
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; /* 関数の戻り値。照合成功か判定 */

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

    /* パターンは入力 p. 98 */
    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);   /* 失敗関数の作成結果を出力 */

   /* 以下、配列fの値を用いながら、kmp法で照合 */




    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で不一致のときの特例。先頭から異なるときの値の設定 */

    /* 以下、配列fの値を求めていく部分 */


}


/* 文字列の最後には\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++;
    }
}