这是一个改进的字符串匹配算法，提供更快的关键词搜索功能。介绍这个可以从分析我们肉眼查找关键词时的做法做起。

这儿有一个串串，假设我们要找到关键词abababca，就是下面那一行玩意

ABABABABCA

ABABABCA

经过观察发现，在匹配位置(标红)出问题前一共有6个字符匹配成功，这六个字符组成的字符串在原串和模式串中是一样的 而且这个串“ABABAB”有一个特点，它的前4个字符和后4个字符是一样的，因此下一次匹配的时候,可以略去前四个字符(标蓝)直接从第五位开始匹配

也就是说，下一次匹配初始位置 = 重复串长度值 + 1             （注意，原串中匹配位置不会发生变化）

ABABABABCA

      ABABABCA

可以发现，如果知道在某字符失配前吻合的字符串中，首尾有多长的部分是重复的，那就可以节约大量的匹配时间 更快加入游戏

针对这个问题，可以建立一个一维数组来存储，以在匹配时直接读取数据。扫描思路很简单，每次错开一位和自己匹配，匹配成功多长就是重复了多少位。具体过程参考下头的图：其中next数组存储 “最长相等的前缀和后缀子串”

 

应该注意到了next的元素编号似乎后移了一位吧？回头看看绿字就能理解了。为了方便起见，next数组的首位即next[0]手动设置为为-1，表示第一位就失去同步的情况。这样在匹配的时候，只要在某一位出现不匹配，将这个值代入next[]就可以知道下一次匹配从第几位开始。

下面贴出我在参考了一些其他代码后写出的拙劣代码，用以实现对给出的关键词串求出next数组：

void Ne_xt(char* msc, int* next)

{
   int i = 0, j = -1;
   next[0] = -1;
   while( i < strlen(msc) )
        {   if( msc[i] == msc[j] || j == -1 )
               { i++; j++; next[i]=j; }
              else
                { j=next[j]; } 
       /*注意这事实上已经应用了KMP算法的思路进行自我匹配，j的位置就是失配点前的位置，next[j]即是获取从开头算起有多少重复的字符，而
由于数组从0开始标号，next[j]本身能够代表重复部分的下一位即第(j+1)个字符的情况。 */
        }
}

在得到了next数组之后，算法的关键已经解决。接下来编写另一程序实现KMP算法，在实际使用时会调用Ne_xt函数。

int KMP(char* A, char* B)
//输入两个字符串指针，返回首字符位置，-1为不存在
{
   int i=0, j=0;
   int next[strlen(B)];
   Ne_xt(B,next);
   while( i<strlen(A) && j<strlen(B) )
   {
      if( A[i] == B[j] || j == -1 )
        { i++; j++; }
      else
        { j = next[j]; } 
   }

      if( j == strlen(B) )
         return i-j; //成功返回目标首字符位置
      else
         return -1;  //失败返回-1
}