bmMatch  Boyer-Mooreによる文字列照合アルゴリズム
bmSkip   シフト表１の作成
bmNext   シフト表２の作成

文字列照合
    char *bmMatch(char *text, int len, char *pattern,
                  int patlen, int *skip, int *next);

シフト表１の作成
    int bmSkip(int *skip, int slen, char *pattern, int patlen);

シフト表２の作成
    int bmNext(int *next, int nlen, char *pattern, int patlen);

文字列照合関数において
    text     （入力）テキスト
    len      （入力）テキストの長さ
    pattern  （入力）照合パターン
    patlen   （入力）照合パターンの長さ
    skip     （入力）シフト表１
    next     （入力）シフト表２

シフト表１の作成関数において
    skip     （入出力）シフト表１
    slen     （入力）　skip配列の長さ
    pattern  （入力）　照合パターン
    patlen   （入力）　照合パターンの長さ

シフト表２の作成関数において
    next     （入出力）シフト表２
    nlen     （入力）　next配列の長さ
    pattern  （入力）　照合パターン
    patlen   （入力）　照合パターンの長さ

文字列照合関数について
    照合パターンがテキストから見つかった場合はそのポインタ、
    見つからなかった場合は 0 (NULL)。

シフト表１の作成関数について
    シフト表１を正常に作成できた場合は 0、失敗した場合は -1。

シフト表２の作成関数について
    シフト表２を正常に作成できた場合は 0、失敗した場合は -1。

bmSkip()とbmNext() を呼び出してシフト表を作成した後、文字列照合関数
bmMatch() を利用すること。

なお、漢字かな交じりの文字列照合には未対応である。

char *bmMatch(char *text, int len, char *pattern, int patlen,int *skip, int *next){
    int i, j;

    i = patlen - 1;
    while (i < len) {
        j = patlen - 1;
        while (j >= 0 && text[i] == pattern[j]) {
            i--;
            j--;
        }
        if (j < 0) return text + i + 1;
        if (skip[text[i] & 0x00ff] >= next[j])
            i += skip[text[i] & 0x00ff];
        else i += next[j];
    }
    return NULL;
}

int bmSkip(int *skip, int slen, char *pattern, int patlen){
    int j;

    if (slen < 256) return -1;
    for (j = 0; j < 256; j++) skip[j] = patlen;
    for (j = 0; j < patlen - 1; j++)
        skip[pattern[j] & 0x00ff] = patlen-1-j;
    return 0;
}

int bmNext(int *next, int nlen, char *pattern, int patlen){
    int  j, k, s;
    int  *g;

    if (nlen < patlen) return -1;
    if ((g = (int *)malloc(sizeof(int)*patlen)) == NULL) return -1;
    for (j = 0; j < patlen; j++) next[j] = 2*patlen - 1 - j;
    j = patlen;
    for (k = patlen - 1; k >= 0; k--) {
        g[k] = j;
        while (j != patlen && pattern[j] != pattern[k]) {
            next[j] = (next[j] <= patlen-1-k) ? next[j] : patlen-1-k;
            j = g[j];
        }
        j--;
    }
    s = j;
    for (j = 0; j < patlen; j++) {
        next[j] = (next[j] <= s+patlen-j) ? next[j] : s+patlen-j;
        if (j >= s) s = g[s];
    }
    free(g);
    return 0;
}

BMアルゴリズムの長所は、テキスト中の文字の大部分を調べずにすむ可能 性があることである。素朴なアルゴリズムやKMPアルゴリズムでは、テキス トの中の文字をそれぞれ１回は調べなければならない。比較は最低でも n 回になる。これに対して、BMアルゴリズムでは n/m 個（nはテキストの長 さ、mは照合パターンの長さを表す）の文字とだけ比較すればよいことが ある。これによって、特に照合パターンが長いときに、計算時間の大幅な 短縮が期待できる。

この特徴から、BMアルゴリズムは、実用上きわめて重要なアルゴリズムと 見なされている。テキスト探索の使用頻度が高いだけにその価値は大きい。

BMアルゴリズムも、素朴なアルゴリズムと同様、テキストを左から順に調 べていく。しかし、いったんテキスト上の位置がきまったら、照合パターン については、逆に右から左に向かって調べる。照合パターンを逆向きに調べ ることがBMアルゴリズムの要点である。もちろん、照合を進めるにあたって は、それ以前に行った比較の結果として得られた情報をできるだけ活用して、 比較の回数を減らすように努める。これはKMPアルゴリズムと同様である。