読者です 読者をやめる 読者になる 読者になる

KMP法のお勉強

だが解説は面倒なのでしない。
maketableさえ覚えればsearchはそれと形が似ているので簡単そう。

#include <cstdio>

void kmp_maketable(const char *key, int *table)
{
    table[0]=-1;table[1]=0;
    int i=2,j=0;
    while(i==0 || key[i-1]) {
        if(key[i-1] == key[j]) {
            table[i++] = ++j;
        } else if(j>0) {
            j = table[j];
        } else {
            table[i++] = 0;
        }
    }
}
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 kmp_search(const char *str, const char *key, const int *table)
{
    int i=0,j=0;
    while(str[i]) {
        if(str[i]==key[j]) {
            if(!key[j+1]) {
                printf("B: %d\n", i-j);
            }
            i++, ++j;
        } else if(j>0) {
            j = table[j];
        } else {
            i++;
        }
    }
}

int main(int argc, char **argv)
{
    const char *str = "ABCABCABCDABCABCDABCBCABCABCDABC";
    const char *key = "ABCABCDABC";
    int table[100];
    simple_search(str, key);
    kmp_maketable(key, table);
    kmp_search(str, key, table);
    return 0;
}