本文共 3959 字，大约阅读时间需要 13 分钟。

KMP算法

简介

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

---

原理

KMP算法对朴素算法的优化在于通过利用目标字符串的性质（某些段前缀与后缀相同）来减少了指针的回溯，从而减少运算。

于是KMP最重要和难理解的部分就是如何求解目标字符串的前缀和后缀相同的段，如何利用性质减少运算。

下面分为这两个部分来解释。

---

求解目标字符串最长的相同的前缀和后缀

首先解释定义

前缀：字符串从头开始到任意位置的子串（这个子串不能为本身）。 后缀：字符串从任意位置开始到尾结束的子串（这个子串不能为本身）。 最长的相同的前缀和后缀：例如ababab 前缀有：a,ab,aba,abab,ababa 后缀有：b,ab,bab,abab,babab 相同的前缀后缀有：ab，abab 最长的相同前缀后缀时：abab

朴素算法求解：

我们需要找到所有的前缀与后缀，他们有n对。然后依次比较找到最大的，这样时间复杂度是$O(n^2)$。

利用已经判断的重复子串来减少运算：

这里有点动态规划的意味，我们假设从头到n位置的子串最大的相同前缀后缀的长度为$l[n]$。 现在考虑能否利用$l[0]$~$l[n]$来减少$l[n+1]$的运算。 当$s[n+1]==s[l[n]]$时这是显而易见的，$l[n+1]=l[n]+1$。 例如：bbbabbb的最大的是bbb，长度为3。 再判断bbbabbba时只需判断$a_{(3)}==a_{(7)}$，这时最大的是bbba，长度为4。

如果$s[n+1]==s[l[n]]$时，才是关键。

我们仍然可以利用已经判断过得重叠子串，但我们要求其必须比最长的前缀后缀小，例如次长的前缀后缀。 假设$ml[n]$为次长的相同前缀后缀长度。

需要知道的是在$l[n+1]$之前我们已经求解了所有的$l[0]$~$l[n]$

通过$l[n]$我们知道有：

$s[0:l[n]-1]==s[n-l[n]+1:n]$

（最长的前缀与最长的后缀相同）

$s[0:l[n]-1]$作为一个子字符串它的最长相同前缀后缀为$l[l[n]-1]$

所以有：

$s[0:l[l[n]-1]]==s[(l[n]-1)-l[l[n]-1]+1:l[n]-1]$

令

$t=l[n]-1有$

$s[0:l[t]-1]==s[t-l[t]+1:t]$

结合一式我们可知$s[n-l[n]+1:n]$的最长相同前缀后缀也为$l[l[n]-1]$

所以有：

$s[n-l[n]+1:n-l[n]+l[t]]==s[n-l[t]+1:n]$

综上有：

$s[0:l[t]-1]==s[t-l[t]+1:t]==s[n-l[n]+1:n-l[n]+l[t]]==s[n-l[t]+1:n]$

$s[0:l[t]-1]==s[n-l[t]+1:n]$

这样我们就找到了次长的相同前缀后缀

$ml[n]=l[l[n]-1]$

接下来使用$ml[n]$来重复上述，直到求出了$l[n+1]$。

---

利用目标子串的性质来减少指针回溯

朴素算法中我们需要依次将目标串的头与匹配串的各个位置对齐，进而比较相同，这样的时间复杂度是$O(n^2)$。

利用子串相同的前缀与后缀减少运算。

如图1，2，3，4是相同的部分，那么我们在判断完后可以直接跳过蓝色部分的判断，直接跳到2处开始判断A是否等于C。 这样就减少了大量运算。 当然除了使用最长前后缀优化后，还需要使用次长前后缀优化（求次长前缀的方法与之前相同），直到完全匹匹配。

---

代码

这里并没有直接使用$l[n]$而是为了代码方便进行了变形

$k=l[n]-1$

void cal_next(char *str, int *next, int len){
       next[0] = -1;//next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀    int k = -1;//k初始化为-1    for (int q = 1; q <= len-1; q++)    {
           while (k > -1 && str[k + 1] != str[q])//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。        {
               k = next[k];//往前回溯        }        if (str[k + 1] == str[q])//如果相同，k++        {
               k = k + 1;        }        next[q] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]    }}

int KMP(char *str, int slen, char *ptr, int plen){
       int *next = new int[plen];    cal_next(ptr, next, plen);//计算next数组    int k = -1;    for (int i = 0; i < slen; i++)    {
           while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）            k = next[k];//往前回溯        if (ptr[k + 1] == str[i])            k = k + 1;        if (k == plen-1)//说明k移动到ptr的最末端        {
               //cout << "在位置" << i-plen+1<< endl;            //k = -1;//重新初始化，寻找下一个            //i = i - plen + 1;//i定位到该位置，外层for循环i++可以继续找下一个（这里默认存在两个匹配字符串可以部分重叠）            return i-plen+1;//返回相应的位置        }    }    return -1;  }

转载地址：http://vwcmz.baihongyu.com/