}

     printf("\n");

     return 0;

}

三．KMP原理讲解及附录本人编写的KMP代码  

1>原理基本构造：

由定义知next[1]=0;

设next[j]=k,这表明在模式串中存在下列关系：

    ‘P1…Pk-1’ = ‘Pj-k+1…Pj-1’                   1》

其中k为满足1<k<j的某个值，并且不可能存在k'>k满足等式1》，此时next[j+1]=?

可能有两种情况：

(1) 若Pk=Pj，则表明在模式串中

‘P1…Pk’ = ‘Pj-k+1…Pj’                         2》

并且不可能存在k'>k满足等式2》，这就是说next[j+1]=k+1,即

next[j+1]=next[j] + 1                        3》

        思考一下为什么？

   (2)若Pk≠Pj,则表明在模式串中

         ‘P1…Pk’≠ ‘Pj-k+1…Pj’                      

      此时可把next函数值的问题看成是一个模式匹配的问题，整个模式串即是主串又是     模式串，而当前在匹配的过程中已有Pj-k+1=P1，Pj-k+2=P2，…，Pj-1=Pk-1,则当

      Pj≠Pk时应将模式向右滑动到模式中的第next[k]个字符和主串中的第j个字符相比 

      较。若next[k]=k',且Pj=Pk'，则说明在主串中第j+1个字符之前存在一个长度为为

      K'（即next[k])的最后子串，和模式中从首字符起长度为k'的子串相等，

 ‘P1…Pk'’= ‘Pj-k'+1…Pj’（1<k'<k<j)          4》

     这就是说 next[j+1]=k'+1

` 即next[j+1]=next[k]+1;

     同理若Pj≠Pk'则将模式继续向右滑动直至将模式中第next[k']个字符和Pj对齐，……

     依次类推，直至Pj和模式中某个字符匹配成功，或者不存在任何k'（1<k'<j)满足4》

     则

next[j+1]=1;

2>KMP源代码 ：

   /*串的模式匹配算法*/

// 文件:cpp1.cpp

// 程序员：caoxing

// 日期：２０１１－３－２４

// 概要：处理字符串的匹配问题

// 组成：由两个自定义函数和一个主函数：

// get_nextval(char T[ ],int nextval[ ]);

// Index_KMP(char T[ ],char S[ ],int pos,int nextval[ ]);

// main( );

// 目的：为文本编辑程序和建立词索引表程序做基础

    #include<stdio.h>

#include<string.h>

void get_nextval(char T[ ],int nextval[ ])

{//求模式串Ｔ的next函数修正值并存入数组nextval.

   int i=1,j=0;

   nextval[1]=0;

   int length;

   length=strlen(T);

   while(i<length)

   {

        if(j==0||T==T[j])