KMP文字列パターンマッチングアルゴリズム

文字列パターンマッチングについては,暫定的にターゲット列の中のパターン列が現れる最初の位置を見つけることを目的とする.
本文は参照した
http://kenby.iteye.com/blog/1025599
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
KMPアルゴリズムの原理と実装を詳細に紹介した2つの論文.
今、私の体験を少し増やします.
KMPアルゴリズムは,従来の暴力アルゴリズムに比べて,1文字1文字の前方移動ではなく,パターン列接頭辞配列に従ってジャンプ的に前進する.
next[]配列:パターン列の前n文字のうち前後対称の個数を表す.
000#xxx 0000で
例:
アルゴリズムの必要性:デフォルトnext[0]=next[1]=0;
next[2] = 1; next[3] = 2; next[4] = 0; next[5] = 0; next[6] =  0; next7] = 0; next[8] = 1; next9] = 2; next10] = 3; next[11] = 3;
これらの接頭辞配列をマッチングする方法について説明します.
例えば、前のn文字が一致し、n+1文字目が一致しないことが判明した場合、モード列をn-next[n]距離だけ前に移動し、p[next[n]]と前回一致したsrc[k]から一致させる.
たとえば
 0000
000#が最初の3つに一致し、4つ目が一致しない場合、3-next[3]=1つの位置を移動し、p[next[3]=p[2]を比較してsrc[]の後に比較を開始する

例えば上図
6文字マッチ
次にnext[6]=2、次に6-2=4の位置を前に移動し、その後

p【next[6]=p[2]で後のデータと比較する.
次にnext[]配列を解く方法について説明します
000#xxx0000
この文字列
まずnext[0]=next【1】=0;

    void compute_prefix(int *next, char *p)  
    {  
        int     i, n, k;  
      
        n = strlen(p);  
        next[1] = next[0] = 0;  
        k = 0;      /*  i       ，k  next[i-1]   */    
        for (i = 2; i <= n; i++) {  
            for (; k != 0 && p[k] != p[i-1]; k = next[k]);  
            if (p[k] == p[i-1]) k++;  
            next[i] = k;  
        }  
    }  

このアルゴリズムの正しさは推すとすぐわかる
KMPアルゴリズムC言語バージョン

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

void compute_prefix(int *next, char *p)
{
    int     i, n, k;

    n = strlen(p);
    next[1] = next[0] = 0;
    k = 0;      /*  i       ，k  next[i-1]   */
    for (i = 2; i <= n; i++) {
        for (; k != 0 && p[k] != p[i-1]; k = next[k]);
        if (p[k] == p[i-1]) k++;
        next[i] = k;
    }
}

void kmp_match(char* text,char* p,int* next)
{
    int m,n,q,s;
    m = strlen(p);
    n = strlen(text);
    s = 0;// s       text         
    q = 0;// q               
    while(s<n)
    {
        for(q=next[q];q<m&&p[q]==text[s];s++,q++);
        if(q==0)s++;
        else if(q==m){
             printf("pattern occurs with shift %d
", s-m);
        }
    }

}
int main()
{
    int     next[101], n;
    char    *p = "000";
    char    *text = "000#xxx0000";

    compute_prefix(next, p);
    kmp_match(text, p, next);
    int i = 0;
    for(;i<4;i++)
    {
        printf("%d ",next[i]);
    }
    return 0;
}