アルゴリズムKMP

はい、接尾辞の配列を学び終わって、いっそACオートマチックも習いたいと思って、それからKMPの基礎が必要らしいことを発見して、ついでに復習して、ついでにブログを書いて、閲覧量を増やすつもりです.
KMPアルゴリズムとは何か、その名の通り(毛片を見て、みんなできるでしょう、、、黄ネタがおとなしくて、恥ずかしいです)K、M、Pの3人がほぼ同時に発見した線形文字列マッチングアルゴリズムです.はっきり言って、短いa列と長いb列で、a列がb列のある位置に一致するかどうかを見せます.
従来の方法は、n^2暴力マッチングであり、ランダムなデータの下では、このアルゴリズムは非常に効率的ですが、試験はあなたを喜ばせることはありません.だから、KMPアルゴリズムを学ぶ必要があります.
まずテンプレートを1つ与えます

struct kmp
{
    char a[20000],b[2000000];
    int nxt[20000];
    int lena,lenb;
    void scanfa()
    {
        scanf("%s",a);
    }
    void scanfb()
    {
        scanf("%s",b);
    }
    void nxt_init()
    {
        int p = 0;
        for (int i = 1;i < lena;i++)
        {
            while (p && a[p] != a[i]) p = nxt[p - 1];
            if (a[p] == a[i]) p++;
            nxt[i] = p;
        }
    }
    kmp()
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(nxt,0,sizeof(nxt));
    }
    void init()
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(nxt,0,sizeof(nxt));
    }
    int match()
    {
        lena = strlen(a);
        lenb = strlen(b);
        nxt_init();
        int p = 0;
        for (int i = 0;i < lenb;i++)
        {
            while (p && a[p] != b[i]) p = nxt[p - 1];
            if (a[p] == b[i]) p++;
            if (p == lena) return i - lena + 2;
        }
        return -1;
    }
};

それから私たちは一歩一歩考えて、私たちは伝統的なn^2アルゴリズムの中で何を浪費しましたか.私たちは毎回、短い列の長いlenaかもしれません.私たちはlena-1ビットにマッチングできませんでした.このように、私たちは次からa列にマッチングし始めます.明らかに前にマッチングしたlena-1ビットは浪費しました.だから、kmpアルゴリズムの核心は前にマッチングしました.私はもうマッチングをしません.
kmpアルゴリズムを行うには,まずコア,nxt配列を求める必要がある.
nxt配列の例を示す
a b  r  a c a d a b r a 0 0 0 1 0 1 0 1 2 3 4
説明を容易にするために,短い列はa列,長い列はb列と定義した.
もし私たちがa列マッチングb列で0位に失敗したら、明らかにbの次のビットからaの0位からマッチングを開始します.
同じようにいくつかの例を挙げます.例えば、b列がaにマッチングしたときに最後のaマッチングに失敗した場合、bの下でaの4位からマッチングを開始することができます.なぜですか.0-4位と7-9位は同じです.明らかに私たちは前のマッチングから最後のaにマッチングして失敗しました.では、bの次のビットからマッチングを開始します.明らかに、私たちは下の4のところから下にマッチングすることができて、下の0-3、明らかに必ずマッチングして、あなたのbマッチングに失敗したあの1人の前の3人のため、aの中の後ろのabrに等しくて、やっと最後にマッチングすることができて、それでは明らかに私たちはマッチングに失敗した位置から、a文字列の試験前のabrからマッチングするのは問題がなくて、しかもすでに0-2位のマッチングに成功しました.では、このnxt配列をどのように求めるかを考えてみましょう.もし私たちのボールがnxt[i]であれば、明らかにnxt[i-1]を見る必要があります.nxt[i-1]が指している下付き記号がa[i]であれば、nxt[i]=nxt[i-1]+1であることは明らかです.そうしないと、nxtを探し続けます.
nxtを求めた後、私たちはとても楽しくマッチングすることができて、b列の0ビットから、毎回待たないならば、nxtに沿ってa列を0までジャンプして、もし等しいならば次のビットを比較して、もし最後のa列が頭に比べて、発見したことを証明して、帰って、詳しくて、上のコードを参考することができます.