Knuth-Morris-Pratt（KMP）算法【详解】

前言

笔者在学习字符串的过程中，接触到求子字符串位置的问题，除了暴力解法外了解到有一种名为KMP（烤馍片）的巧妙算法也顺便了解了一下发明者之一的“神”Kunth的履历，但不在此赘述。虽然网上有很多详细图解之类，但我还是不能充分理解。在看完Tushar Roy的讲解后才恍然大悟，本文主要根据他的讲解，结合自己的思考在此写出我的理解。

---

一、从问题谈起，如何最直接地搜索一个字符串？

• 示例：
  给定字符串是absdglx,目标字符串是sdgl，给每个字符标上序号，分别是m0,m1,m2,m3,m4,m5,m6,n0,n1,n2,n3。最直接的搜索并定位目标字符串的方法就是将目标字符串的每个字符给定字符串的字符逐一比较。
• 从m0，n0开始，若匹配则两字符串都从比较的字符往后移动一个字符，继续进行比较；若不相同，则给定字符串回到从起始比较位往后移动一个字符的位置，目标字符串回到n0从头开始比较，直到在给定字符串超过最后一个字符m7前，目标字符串匹配完最后一个字符n3，即搜索到目标字符串。
• 要将上述过程通过编程实现，我们可以用两个指针i,j分别指向给定字符串和目标字符串，按上述过程进行指针的后移和回退，直到i或j指向字符串的最后一个字符。

二、实现优化的kmp算法如何操作？

我们可以发现上文朴素(暴力)算法的不便和存在大量低效、重复的匹配操作，那么我们可不可以通过某些目标字符串本身特性来减少回退而多进行回溯，提高效率。

1.引入前缀数组

• 前缀数组的每个元素对应着目标字符串的每个字符，其元素表示了该字符前的子字符串（包括该字符）中的最长的相等的前缀和后缀的长度，即前文所指的目标字符串的某些特性。
  举例：abcabcd的前缀数组可以用下面这个表格来表示。

  a	b	c	a	b	c	d
  0	0	0	1	2	3	0

• 我们用一个例子来详细解释如何手推前缀数组,过程中会用到前缀和回溯的思想。
  1.abcdabca使用两个指针i,j分别指向a,b,i和j指向的元素显然为0，将j向后移动，j移动到j移动到第二个a时有了相同前后缀元素记为1，然后将i和j都向后移动j指向b相同前后缀长为2，数组元素记为2，再次将i和j向后移动，j指向c同理，当j指向末尾的a时两指针所指字符不同，需要进行回溯。观察到j指针所指字符的前一个字符对应元素为0，即没有相同前后缀，则将j回退至首字符，此时i和j所指字符均为a，则i所指字符对应元素记为1。该字符串前缀数组即为00001231。

2.给定字符串和目标字符串分别如何回溯？

• 举例：给定字符串abxabcabcaby,目标字符串abcaby,对应前缀数组为000120。（同样使用i j指针但分别指向给定字符串和目标字符串）
  两字符串前两个字符匹配，第三个字符分别为x和c不匹配，j前一字符对应元素为0，j回到首位指向a仍与x不匹配，j不移动，将i往后移动指向a与j所指匹配，i和j都往后移动。同理继续匹配直到i指向c，j指向y不匹配，j前一字符对应元素为2，j回溯到第三个字符c与i匹配，i和j都往后移动继续匹配直到最后完成匹配。

三、如何用代码来实现kmp算法？

同样主要分为两步，

1. 计算目标字符串的前缀数组

• 前缀数组定义为prefix[],j和i分别指向第一、二个字符，让i遍历目标字符串每个字符，j = prefix[j-1]就是j回溯至j所指前一个字符对应元素的位置。

   void Prefix(char* pattern, int* prefix, int len)
  {
      int j = 0;
      prefix[0] = 0;
      int i= 1;
      while(i<len){
          if(pattern[i]==pattern[j]){
              j++;
              prefix[i] = j;
              i++;
          }else{
              if (j!=0)
              {   
                  j = prefix[j-1];
              }else{
                  prefix[i] = 0;
                  i++;
              }
          }
      }
  }

2.借助前缀数组进行字符串的匹配

• pattern为目标字符串，text为给定字符串，i和j分别指向给定字符串和目标字符串，同样遍历给定字符串，若j指向了目标字符串最后一个字符，则i-j为text中pattern的首字符位置。

  void kmpsearch(char*text,char*pattern)
  { 
      int len = strlen(pattern);
      int wid = strlen(text);
      int prefix[len];
      Prefix(pattern,prefix,len);
      int i=0,j=0;
  
      while (i < wid)
      {
          if(pattern[j]==text[i]){
              i++;
              j++;
          }
          if(j==len){
             printf("%d\n",i-j);
             j = prefix[j-1];
          }else if(i<wid&&pattern[j]!=text[i]){
             if(j!=0){
              j = prefix[j-1];
             }else{
              i++;
             }
          }
      }
  }

总结

本文详细解释了kmp算法如何实现，kmp算法通过目标字符串由自身特性生成的前缀数组来减少回溯的过程，建议亲自动手推一推生成前缀数组和模式匹配的过程，这样可以更好地理解其思想和原理。

如果发现文章中存在错误敬请批评指正，感谢您的阅读。