C言語でBM法

早速実装

アルゴリズムの説明は他で十分だからとにかく実装例が見てみたい！という人のためにc言語での実装の一例を置いておく。

boyerMoore.c

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

int next_step(int table[], char target, int remain);
int boyerMooreSearch(const char str[], const char pat[]);
#define MAX_LEN 100

int main() {
    char str[ MAX_LEN ];
    char pat[ MAX_LEN ];

    printf("Enter the string: ");
    fgets(str, MAX_LEN, stdin);
    printf("Enter the pattern: ");
    fgets(pat, MAX_LEN, stdin);

    printf("The result is: %d\n", boyerMooreSearch(str, pat));

    return 0;
}

int next_step(int table[], char target, int remain) {
    /* ループ防止のために確認する */
    if (table[ target ] > remain) {
        /* ずらし表から値を取得する */
        return (table[ target ]);
    } else {
        /* 照合を開始した地点の次の文字に進める */
        return (remain);
    }
}

/*
 * [機能]: "txt[]"から、"pat[]"を探索する
 * [引数]: char txt[] : 探索する元の配列
 *       : char pat[] : 探索する対象の配列
 * [戻り値]:int pt: 探索した配列が配列元の配列の何文字目に発見されたか
 *          int -1: 探索した結果、一つも見つからなかった時
 */
int boyerMooreSearch(const char str[], const char pat[]) {

    if (strstr(str, pat) == NULL) {
        return (-1);
    }
    int pt;                    /* txtをなぞるカーソル */
    int pp;                    /* patをなぞるカーソル */
    int txt_len = strlen(str); /* txtの文字数 */
    int pat_len = strlen(pat); /* patの文字数 */
    int skip[ UCHAR_MAX + 1 ];
    /* スキップテーブル */
    for (pt = 0; pt < UCHAR_MAX; pt++) {
        /* スキップテーブルの作成 */
        skip[ pt ] = pat_len;
    }
    for (pt = 0; pt < pat_len - 1; pt++) {
        skip[ pat[ pt ] ] = pat_len - pt - 1;
    }

    pt = pp = pat_len - 1; /* 比較位置をパターン末尾にする */
    while ((pt < txt_len) && (pp >= 0)) {

        if (str[ pt ] != pat[ pp ]) {
            /* ずらし表を参照して、次の比較位置を設定する */
            pt += next_step(skip, str[ pt ], (pat_len - pp));
            pp = pat_len - 1; /* 比較位置をパターン末尾にする */
        } else {
            /* 文字が一致したので、前の文字を照合していく */
            pp--;
            pt--;
        }
    }

    if (pp < 0) {
        return pt + 1;
    } else {
        return 0;
    }
    return (-1);
}