また「KMP」に会いました

同じ http://blog.csdn.net/shanshanpt/article/details/8679459 ,全部思い出版です
>:KMPのいくつかの概念の紹介は大丈夫です.ネット上は至るところにあります.ここは整理のためだけです.
>:ネットで見た文章は全部「next」配列とi、jポインタの移動から言ったものです.ここも同じですが、違うのは、もっとはっきり言いたいことです.
 >: 従来のBFアルゴリズムとKMPの違いは何ですか?
      BF:元の列:B A B A B ...
               サブストリップ: B A B A D    この時点でマッチしません.次の文字から開始します.   元の列:A B A B…
--------------------------------------------------------------子串:     A B A D---------------------------------------------------------
     そしてまた探し続けます.そうすると、私たちの前期のマッチングは無駄になります.KMPはすでにやった仕事を最大限に利用します.
     
     KMP:元の列:B A B A＿D＿A…
                  サブ串:B A B A D.     
      よくないです.合っていないことが分かりました.どうすればいいですか?KMPはBFのようにバカではなく、最初からやり直すのです.--->前の文字列に対して、境界を見つけたいです.何ができますか?一番前のmの長さの文字列(前から数えてmのchar)と一番後ろのmの文字列を作ることができます.(後ろから数mのcharを数えます.ここで言っているのは前に成功した部分ですよ～^_^)同じです.何になりますか?
                直列:B A B A B A D A…
                サブストリップ:      B A B A D    じゃ、次のB Aを見られます. 前にマッチした文字列が等しい場合です.
                                                         前は文字列のDが合っていなかったということを知っていますので、頭のmの長さの文字列と尾のmの長さの文字列が等しいと見つけたら、頭のmの長さが分かります.
                                                         元の尾部mの長さに移動すると、元の列に対応するmの長さが必ず一致します.これはKmpとBFの違いの鍵です.
               もう一つの例を見ます.
               直列:B A C B A B A D A…
               サブ串:B A C B A D .
               KMP処理後、次のようになります.
                    直列:B A C B A B A D A…
                    サブストリップ:          B A C B A D      赤い色 BとDは前の不一致のところで、緑色の3つのB Aは上のKMPの処理の結果です.
      >:  こんなに多く話して、みんなはすべてむだ話だと思うことができて、ほほほ、下は重要なnext配列が解を求めます.
    >: next[0]=-1を定義し、next[j]=kを仮定して、 すなわち、M[0...k-1]==M[j-k...j-1]である.
     >: その後、下にスキャンします.M[j]==M[k]なら、M[0.k]==M[j-k,j]があります.明らかに、next[j+1]=next[j]==k、next[j]=kがあります. 
    >:                           もしM[j]!=M[k]にマッチして失敗したら、k=next[k]というように書いていますが、なぜですか?私たちはよく考えてみてもいいです.上のM[j]==M[k]に直接+1
    私のnextを得ることができます.ここでは同じではないです.Mの前の文字列から処理できます.つまり、M[next[k]から可能です.
コードを書きます.

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

void get_next( char *tmp,int *next )
{
    int j,k;
    int len = strlen( tmp );

    next[0] = -1;                            //     
    j = 0;
    k = -1;

    while( j < len - 1 )
    {
        if( k == -1 || tmp[j] == tmp[k] )    // tmp[j]==tmp[k]
        {
			j++;
			k++;

            if( tmp[j] == tmp[k] )	   // if  ，      next   
	    {                               
                next[j] = next[k];
	    }
            else
	    {
                next[j] = k;                
	    }
        }
        else                   
	{
            k = next[k];                    //      ，              ！ 
	}
    }
}

int KMP( char *s,char *tmp, int next[] )
{
    int i = 0,j = 0, len_s = strlen( s ), len_p = strlen( tmp );

    while( i < len_s )
    {
        if( j == -1 || s[i] == tmp[j] )  //      ||   char    
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];       //      i   (    BF    )
        }

        if( j == len_p )       //      
	{
            return i - len_p;  //       
	}
    }

    return -1;                 //     
}



int main()
{
	char str[80], sub_str[20];
	int  next[100], first_at;

	while( gets( str ) )
	{
		gets( sub_str );
		
		get_next( sub_str,next );             //     next   
		first_at = KMP( str, sub_str, next ); //  

		if( first_at != -1 )
		{
			printf("At: %d
", first_at);
		}
		else
		{
			printf("No cmp...
");
		}
	}

	return 0;
}