KMP法+ボイアームーア=有限オートマトン

という気がしてきたので、文字列検索の有限オートマトン化をしてみた。

…普通にこれでいいじゃん！

有限オートマトンの生成にかかる時間およびメモリはn=キーサイズ,c=文字の種類とおいてO(cn)なので、そこで少し遅れをとるけど、検索が非常にシンプルで高速(検索対象文字列を一回しか参照しない)になる。

検索文字列が小さくて、検索対象文字列が大きいときに有効だと思う。

#include <cstdio>

void simple_search(const char *str, const char *key)
{
    for(int i = 0; str[i]; i++) {
        int j;
        for(j = 0; str[i+j] && key[j] && str[i+j]==key[j]; j++) {
        }
        if(!key[j]) {
            printf("A: %d\n", i);
        }
    }
}

void makefsm(const char *key, int (*fsm)[256])
{
    for(int ch = 0; ch < 256; ch++) {
        if(ch == key[0]) {
            fsm[0][ch] = 1;
        } else {
            fsm[0][ch] = 0;
        }
    }
    int j = 0;
    for(int i = 1; key[i-1]; i++) {
        for(int ch = 0; ch < 256; ch++) {
            if(ch == (unsigned char)key[i]) {
                fsm[i][ch] = i+1;
            } else {
                fsm[i][ch] = fsm[j][ch];
            }
        }
        if(key[i] == key[j]) {
            j++;
        } else {
            j = 0;
        }
    }
}
void fsm_search(const char *str, const char *key, const int (*fsm)[256])
{
    int state = 0;
    for(int i = 0; str[i]; i++) {
        int ch = (unsigned char)str[i];
        state = fsm[state][ch];
        if(!key[state])printf("B: %d\n", i-state+1);
    }
}

int main(int argc, char **argv)
{
    const char *str = "ABCABCABCDABCABCDABCBCABCABCDABCCCCABCABCDAB";
    const char *key = "ABCABCDABC";
    int fsm[100][256];
    makefsm(key, fsm);
    simple_search(str, key);
    fsm_search(str, key, fsm);
    return 0;
}