KMP算法总结

KMP算法的用途

KMP算法是一种字符串匹配算法。

设两个字符串s和p，s为文本串，p为待匹配串，s的长度为n，p的长度为n，则最常见的字符串匹配的暴力算法就是遍历字符串s，如果s[0] == p[0]，则继续向后比较，直到字符串匹配完成或者发现不匹配的字符，然后向后继续比较；这样的方法的时间复杂度是O(mn)；而KMP算法则可以将时间复杂度降低到O(m + n)。

KMP算法

KMP算法的主要过程如下：

假设s=“BBC_ABCDAB_ABCDABCDABDE”, p=“ABCDABD”

匹配过程1:

BBC_ABCDAB_ABCDABCDABDE
ABCDABD

匹配过程2:

BBC_ABCDAB_ABCDABCDABDE
 ABCDABD

匹配过程3:

BBC_ABCDAB_ABCDABCDABDE
  ABCDABD

匹配过程4:

BBC_ABCDAB_ABCDABCDABDE
   ABCDABD

匹配过程5:

BBC_ABCDAB_ABCDABCDABDE
    ABCDABD

在这一次匹配过程中，我们可以发现一直到最后一个字母才发生了不匹配的情况。如果是暴力法的话，这里应当继续将字符串p后移一位，来继续匹配过程。但是KMP算法是将字符串p后移4位，也就是移动到下一处AB的位置，得到下一次的匹配。此处失配时，模式串向右移动的距离 = 已匹配字符数 - 失配字符的上一位字符所对应的部分匹配表的值。

匹配过程6:

BBC_ABCDAB_ABCDABCDABDE
        ABCDABD

此时按照和上面相同的方法进行之后匹配，也就是有：

匹配过程7:

BBC_ABCDAB_ABCDABCDABDE
          ABCDABD

匹配过程8:

BBC_ABCDAB_ABCDABCDABDE
           ABCDABD

匹配过程9:

BBC_ABCDAB_ABCDABCDABDE
               ABCDABD

至此匹配成功。

部分匹配表的计算

部分匹配表，也就是最大前缀后缀公共元素长度数组，主要通过递归的方式求解。

设部分匹配表为next数组，假设已知next[j] = k，也就是对于s[0, j]这个子串，如果我们在j处失配，则应当将p后移动j - next[j]，也就在是p[j]之前(p[0, j - 1])，我们所能匹配上的最长前缀应当为p[0, next[j] - 1]。

所以我们首先判断p[k]=p[next[j]]和p[j]是否相等。

如果p[k] == p[j]，则说明next[j + 1]只需要在next[j]的基础上向后延长一位即可，也就是next[j + 1] = next[j] + 1 = k + 1；

如果p[k] != p[j]，则需要重新找到最长匹配数组，令k=next[k]，直到k=0或者找到p[k] == p[j]；

改进

在p[k] == p[j]的情况下，延长一位之后，如果此时p[j] == p[k]依然成立，则在匹配过程中可知，当p[k]和s[i]不匹配的时候，p[j]也必然和s[i]不匹配，因此取next[j] = next[next[j]] = next[k]；否则直接取next[j] = k即可；

代码参考

#include<iostream>
#include<vector>
using namespace std;

vector<int> getNext(string p){
   int n = p.size();
   vector<int> next(n, -1);
   int k = -1, j = 0;
   while(j < n - 1){
      if(k == -1 || p[j] == p[k]){
         j++;
         k++;
         next[j] = (p[j] == p[k] ? next[k]: k);
      }
      else{
         k = next[k];
      }
   }
   return next;
}

int KMP(string s, string p){
   int n = s.size(), m = p.size(), i = 0, j = 0;
   vector<int> next = getNext(p);
   while(i < n && j < m){
      if(j == -1 || s[i] == p[j]){
         i++;
         j++;
      } else {
         j = next[j];
      }
   }
   return j == m ? i - j : -1;
}
int main ()
{
   string s = "BBC_ABCDAB_ABCDABCDABDE";
   string p = "ABCDABD";
   cout << KMP(s, p) << endl; // 输出15
   return 0;
}

参考链接

https://blog.csdn.net/v_july_v/article/details/7041827

Yiming

Coding for fun ~