2013-team4/code/kmp

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
传入 pattern 串
kmp.get_fail(pattern, len);
在 text 中寻找
kmp.find(text, len);
}}}
{{{
const int MAXL = 100;

struct KMP{
    int fail[MAXL], m;
    const char *p;
    void get_fail(const char *p, int l){
        this->p = p; m = l;
        fail[0] = fail[1] = 0;
        for(int i = 1; i < l; i++){
            int j = fail[i];
            while(j != 0 && p[i] != p[j]) j = fail[j];
            fail[i + 1] = p[i] == p[j] ? j + 1 : 0;
        }
    }
    void find(const char *s, int l){
        for(int j = 0, i = 0; i < l; i++){
            while(j != 0 && s[i] != p[j]) j = fail[j];
            if(s[i] == p[j]) j++;
            if(j == m){
                j = fail[j];
                cout << "find at " << i - m + 1 << endl;
            }
        }
    }
};
}}}

传入 pattern 串
kmp.get_fail(pattern, len);
在 text 中寻找
kmp.find(text, len);

const int MAXL = 100;
struct KMP{
    int fail[MAXL], m;
    const char *p;
    void get_fail(const char *p, int l){
        this->p = p; m = l;
        fail[0] = fail[1] = 0;
        for(int i = 1; i < l; i++){
            int j = fail[i];
            while(j != 0 && p[i] != p[j]) j = fail[j];
            fail[i + 1] = p[i] == p[j] ? j + 1 : 0;
        }
    }
    void find(const char *s, int l){
        for(int j = 0, i = 0; i < l; i++){
            while(j != 0 && s[i] != p[j]) j = fail[j];
            if(s[i] == p[j]) j++;
            if(j == m){
                j = fail[j];
                cout << "find at " << i - m + 1 << endl;
            }
        }
    }
};