数据结构（动态规划）：KMP字符串匹配算法！

失配位置-最大相同子串（配成功的串里找，失配下标之前的子串）-1=k（移动距离）

规定：

next[1] = next[0] = 0

next[j]:j是失配位置，所以找模式串中的相同子串（前缀和后缀相等）要从j前找

前缀是：假设失配位置时j，前缀是不包含最后一个字符的字符串

后缀不包含的一个字符串

定义：

Pi表示模式P的前i个字符组成的前缀， next[i] = j表示Pi中的开始j个字符和末尾j个字符是一样的，而且对于前缀Pi来说，

这样的j是最大值。next[i] = j的另外一个定义是：有一个含有j个字符的串，它既是Pi的真前缀，又是Pi的真后缀

我就是发个我的作业：详细的可以看 http://kenby.iteye.com/blog/1025599 里面有较为细节的kmp整体的理解

我刚完全理解，对于描述还很欠缺，大家可以看看大神的文章

#include<stdio.h> // EOF(=^Z或F6),NULL

#include<stdlib.h> // srand( ) ,rand( ),exit(n)

#include<malloc.h> // malloc( ),alloc( ),realloc( )等

#include<limits.h> // INT_MAX等

#include<string.h>

#include<ctype.h>

#include<math.h> // floor(),ceil( ),abs( )

#include<time.h> // clock( ),CLK_TCK,clock_t

#include<iostream>

#define    TRUE          1

 #define     FALSE        0

 #define     OK              1

 #define     ERROR      0

 #define     INFEASIBLE     -1

#define MAXLEN 255    //串最大长度

using namespace std;

typedef struct

 { char  ch[MAXLEN+1];                                         //存储串的一维数组

     int   length;             //串的当前长度

   }SString;

void get_next(SString T, int next[])

{

    int  i= 1; next[1] = 0; int j = 0;

     while( i<T.length)

         {

             if(j==0 || T.ch[i] == T.ch[j])

               {

                  ++i;

                  ++j;

                  next[i] = j;

                }

            else     j = next[j];

         }

}

int Index_KMP (SString S,SString T, int pos,int next[])

{

    int i= pos,j =1;

    while (i<=S.length && j<T.length )   // ‘=’表示搜索到串尾

            /* j<=修改为< ；原因是字符串下标从1开始

            （不是0，等于将模式串串长加1（有效字符串串长不变），所以临界值减1）*/

        {  

            if (j==0 || S.ch[i]==T.ch[j]) {   i++;j++;  }

              else  j=next[j];      /*i不变, j后退*/

           }

     if(j==T.length)  //同理>改为=；很简单，T.length变大啦（+1）

     {

         return i-T.length+1;    /*匹配成功*/

            //这里+1是一样的（和下标从0开始无关，因为本书算法是从下标1开始设计的！）

            //答案同样，因为  T.length变大啦（+1啦），多减去的再加回来！   啊哈！不要崇拜我哦

     }

     else

     {

     return 0;         /*返回不匹配标志*/

     }

}

//acabaabaabcacaabc        本书测试数据

//abaabcac

int main()

{

int next[MAXLEN];

int nextval[MAXLEN];        //没什么用吧...待更

memset(next,0,sizeof(next));

memset(nextval,0,sizeof(nextval));     

     //memset：c++,c；置0，相当于for循环迭代数组赋值为0，更多的请问我的维基百科大哥

SString S, T;     //s主串！

printf("请输入主串：\n");

cin>>S.ch+1;                 //下标1开始

printf("请输入模式串：\n");

S.length=strlen(S.ch);

cin>>T.ch+1;

T.length=strlen(T.ch);

cout<<T.length<<endl;

get_next(T,next);

for(int i=0;i<T.length;i++)             //没啥用，就是看看next数组对不对

    {

        printf("%d ",next[i]);

    }

int t=Index_KMP ( S,T, 1/*pos*/,next);    //pos =1 开始

if(t)

{

printf("匹配成功！");

printf("模式串匹配位置：%d\n",t);

}

else

{

printf("匹配失败！\n");

}

getchar();

getchar();

}

 结果：

9为模式串串长！（下标从1开始，0下标无数据）

0 0 1 1 2 2 3 1 2为next数组

6为匹配成功的位置！

5为模式串串长！（下标从1开始，0下标无数据）

00111为next数组

5为匹配成功的位置！