Knuth-Morris-Pratt 算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

个人心得：比较好理解，只要了解前缀和后缀就好了，就是代码实现得太巧妙太抽象，难以体会和想到，不得不佩服！

KMP算法的关键在于next数组的创建和子字符串的匹配；

next数组里面存放的是要查找的字符串前i个字符串的所有前缀、后缀相等的公共串中，最大的长度值。比如需要查找的一个子串ababcd，next[0]表示子串中前1个字符串即a的前缀和后缀中相等字符串的最大长度，因为a的前缀和后缀没有，故next[0] = 0；对于next[2]，即先求出子串aba的前缀和后缀出来，前缀为a,ab，后缀有ba,a，相等的公共串为a，长度为1，因此next[2] = 1;依次可以求出。

 void getnext(int x[],int next[])

 {

     int i=;

     int j=-;

     next[i]=-;

     while(i<m)

     {

         if(j==-||x[i]==x[j])

         {

             i++;

             j++;

             next[i]=j;

         }

         else

             j=next[j];

     }

 }

然后就是字符串的对比了，注意j=-1只会出现一次，以后就是每次的跳转了，根据对应的next实现代码优化

 int i=,j=;

           while(i<=n&&j<m)

           {

               if(j==-||a[i]==b[j])

               {

                   i++;

                   j++;

               }

               else

                 j=next[j];

           }

 if(j==m)  flag=;

 else flag=-;

巴特西

Knuth-Morris-Pratt 算法

最新文章

热门文章