STEP 3.3 解答例

<問題> テキスト中のパターン照合問題について、簡略化ボイヤームーア(Boyer-Moore)法をプログラム

(注意 : 教科書はフルbm法なので、解答を利用するときは必要なところだけ)


<実行結果>　

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

最後に残っているわかりにくいところ：

その他の例

例題集へ 




  

  

  



  

  

  












  








  
解答例

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

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法でいこう。p.114の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法で照合 */

   while (i >= 0 && j < n) {
       cmp++;
       if (p[i] == t[j]) {/*　一致。前進する */
           i--;
           j--;
       } else { /* 一致しない */
//           printf("j = %d check = %c g = %d\n", j, t[j], g[t[j]]);
           if (g[t[j]] > m - i )
                j = j + g[t[j]]; /* jを進める */
           else  /* パターンを戻しすぎになる場合はjを1つ進めるように */
                j = j + m - i;
           i = m - 1; /* どちらの場合でも、pは最後の要素から */
       }
    }


    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=0; i < 255; i++)
         g[i]= m;     /* まず全部を、パターンの長さ分スキップに設定 */
    for (i=0; i < m - 1 ; i++)
         g[p[i]]= m - 1 - i ;  /* パターン中の文字について再計算 */
                            /* 後ろからどれだけ離れているか */


    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++;
    }
}