STEP 3.3

問題

実行例

[実行例] 
探したい文字列を入力してください :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　（ここまで、テキスト）
g[A]= 5（以下、その文字で不一致。jをいくつスキップさせて、またpの最後尾からチェックを再開するか)
g[B]= 5
g[C]= 5
g[D]= 5
g[E]= 5
g[F]= 5
g[G]= 5
g[H]= 5
g[I]= 5
g[J]= 5
g[K]= 5
g[L]= 5
g[M]= 5
g[N]= 5
g[O]= 5
g[P]= 5
g[Q]= 5
g[R]= 5
g[S]= 5
g[T]= 5
g[U]= 5
g[V]= 5
g[W]= 5
g[X]= 5
g[Y]= 5
g[Z]= 5
g[[]= 5
g[\]= 5
g[]]= 5
g[^]= 5
g[_]= 5
g[`]= 5
g[a]= 2
g[b]= 1
g[c]= 5
g[d]= 5
g[e]= 5
g[f]= 5
g[g]= 5
g[h]= 5
g[i]= 5
g[j]= 5
g[k]= 5
g[l]= 5
g[m]= 5
g[n]= 5
g[o]= 5
g[p]= 5
g[q]= 5
g[r]= 5
g[s]= 5
g[t]= 5
g[u]= 5
g[v]= 5
g[w]= 5
g[x]= 5
g[y]= 5
g[z]= 5
cmp = 6 (教科書の例。比較回数は、1+5 =6)
Pattern ababc is matched at 5

コメント

xxxxdcdexxxx
   abcde
  • eから始まり、Tの先方のdで不一致 
xxxxdcdexxxx
 abcde  　
  • dはパターン中にある。
  • スキップ関数により移動させると、パターンの位置が照合前より戻ってしまう。
  • しかし既に調べてあるはず 
xxxxdcdexxxx
    abcde
  • Pが前に戻るような場合だけは特例
  • dのスキップと関係なく、パターン自身を1つずらすと考えて照合する。
  • 1番目の照合からはパターン全体が一つずれている 
aaaaaaaaaa
 baaaa
  • 特殊な例。Tの文字aで不一致 
aaaaaaaaaa
 baaaa
  • パターンを1つ移動。naiveと近い結果になる

解答例

[解答例（未完）]

例題集 


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

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

int main (void) {
    char t[30];
    char p[10];
    int j;

    /* 教科書の例 */
    strcpy(t, "ababdababccbdcabcadb");
//    strcpy(t, "aaaaaaaaaa"); /* p = "baaaa" */

    printf("探したい文字列を入力してください :");
    scanf("%s", p);

    print_text(t); /* テキストの出力 */

    j = bm(t,p); /* 簡略化bm法でいこう。p114のcompute_gだけを利用する */

    /* 戻り値に応じて、出力文 */
    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 bm(char t[], char p[]) {
    int j;
    int i;
    int g[255]; /* 添え字は1バイト文字アスキーに対応  */
    int m = strlen(p);
    int n = strlen(t);
    int cmp = 0;
    i = m - 1; /* パターンの一番後ろ */
    j = m - 1; /* tの初期値も、そこから */

    compute_g(p, g);

/*  簡略bm法で照合 */


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

    if (i == -1)  /* pを前進しつくした場合は、照合成功  jも１つ前進すぎ */
        return j+1;
    else
        return -1; /* jがNを超えた場合は、照合失敗 */

}


/* パターンに応じて、何文字スキップするか、gテーブルを作る */
void compute_g(char p[], int g[]) {
    int i;
    int m = strlen(p);
/* スキップテーブル gを作成 */



    for (i=65; i < 123 ; i++)  /* gテーブルの出力。デバッグ用 */
        printf("g[%c]= %d \n",i,g[i]);
}


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