KMP算法详解(逻辑分析&数学证明&代码实现)

前言

KMP算法是Knuth、Morris、Pratt三人在BF算法的基础上同时提出的模式匹配的高效算法。本文以字符串匹配问题为例，以通俗易懂的语言对KMP算法进行逻辑分析、数学证明和代码实现。本文需要读者对BF算法有一定了解。阅读本文，读者能够清楚理解KMP算法的核心思想和代码逻辑，并自主实现该算法。

---

优化策略

在BF算法中，每次子串匹配失败后，​​i​​​指针(遍历主串)会回退到​​begin​​​位置的下一个位置，​​j​​指针(遍历子串)会回退到子串的起始位置。假设主串的长度为​​M​​​，子串的长度为​​N​​​，同时回退​​i​​​指针和​​j​​​指针，时间复杂度为​​O(MN)​​。如果字符串中重复字符较多，该算法就显得非常低效。

BF算法：

int BfSolution::BF(string str, string sub)
{
int StBegin = 0;
int SuBegin = 0;
int i = 0;//遍历主串
int j = 0;//遍历子串
while (i < str.length() && j < sub.length())
  {
if (str.at(i) == sub.at(j)) {
i++;
j++;
    }
else {
StBegin++;
i = StBegin;
j = SuBegin;
    }
  }
if (j == sub.length()) {
return StBegin;
  }
else {
return -1;
  }
}

KMP算法的优化策略为：匹配过程中​​i​​不回退，​​j​​回退到一个特定的位置，该位置不一定是起始位置，而需要做特定计算。

下面对​​j​​回退的“特定的位置”做一个说明。需要注意的是，我们的目的是将主串和子串进行匹配，这个过程中​​i​​​不会回退，所以​​j​​回退的位置应该为主串和子串已经尽量匹配的位置。例如下面两个字符串，两字符串在​​i​​​、​​j​​​位置匹配失败，若按照BF算法思想，则应将​​i​​​回退到​​StBegin​​​位置，将​​j​​​回退到起始位置，但是通过观察发现，​​​i​​位置前面的a、b已经和子串的前两个a、b有了很大程度的匹配，所以我们大可以将​​j​​​回退到​​k​​​的位置，​​i​​​不回退，然后​​j​​​从​​k​​​位置继续向后判断和匹配。这里的​​k​​位置即是我们需要的“特定的位置”。也就是说，我们需要找到j位置之前的真子串与i位置之前的真子串有最大程度匹配的位置。寻找该位置的过程，就是​​next​​数组的计算过程。

next数组的计算

---

什么是next数组

上文说到，我们需要计算一个​​j​​匹配失败后回退的位置，这个位置(下标)其实就是​​next​​数组的一个元素。在实际匹配的过程中，每个位置都有可能匹配失败，所以我们需要针对子串的每个位置进行在该位置匹配失败后回退位置的计算，将计算的结果用一个一维数组维护，这个数组就是next数组。next数组记录了在各个位置匹配失败后​​j​​应回退到的位置。

手动计算next数组

我们先尝试手动计算​​next​​​数组，在理解​​next​​​数组的基本计算方法后，再探讨​​next​​​数组计算中的规律，并用代码实现对​​next​​​数组的计算。在下文中继续以​​k​​​作为​​j​​​回退的位置，即​​next​​数组的元素。

通过阅读上文你已经知道，计算​​next​​​数组其实就是要找到​​i​​​、​​j​​位置之前的子串最大程度匹配的位置(​​k​​)。在实际计算过程中，我们只考虑模式串（子串）的内容，所有的计算过程都是针对模式串（子串）的。

继续观察下面的字符串，​​i​​​和​​j​​​既然能够到达当前的位置，就说明​​i​​​之前和​​j​​之前的字符串是完全匹配的，所以​​1​​​部分和​​3​​​部分一定相同，所以我们的问题就转化成了在​​A​​​位置之后、​​B​​​位置之前寻找两个相同的子串，这两个子串其中一个以​​0​​​位置开头，另一个子串以​​j - 1​​位置结尾。不难发现，找到的两个子串的长度即为我们上文得到的位置。

由此我们得到计算​​k​​的方法：寻找两个分别以​​0​​位置开头，以​​j - 1​​位置结尾的两个相同子串，这两个子串的长度即为 ​​k​​ 。

一个练习

计算下面模式串的next数组

答案：

需要注意的是，计算过程中两个子串必须严格遵循“分别以​​0​​位置开头，以​​j - 1​​位置结尾”，两子串重合的情况也包含在内。规定next[0] == -1。

next数组计算中的规律

---

为了下面的说明和证明方便，规定模式串为​​p​​​，从​​i​​​位置回退到的位置依然为​​k​​。

如果我们知道​​next[i] = k​​​，那如何计算​​next[i + 1]​​呢？

p[i] == p[k]时

通过上面的计算我们发现：当​​p[i] == p[k]​​时，有​​next[i + 1] == k + 1​​成立。例如上面练习中的字符串，当i == 4时，有k₁==next[i] == 1，p[i] == 'b' ，p[k] == 'b'，且k₂==next[i + 1] == 2。

下面给出这个规律的数学证明。

数学证明

证明：当​​p[i] == p[k]​​时，若​​p[i] == k​​，则有​​p[i + 1] == k + 1​​

前提：​​next[i] == k​​​成立。为了下文表述方便，用​​p[x]~p[y]​​表示从x位置到y位置的字符串。

假设​​next[i] == k​​​成立，则有​​p[0] ~ p[k - 1] == p[x] ~ p[i - 1]​​​，因为有两子串的长度相等，则有​​k - 1 - 0 == i - 1 - x​​​，得到​​x == i - k​​，即

~~​

另外，由​​p[i] == p[k]​​，可得

~~

综上可得：

对比两式，当​​p[i] == p[k]​​时，若​​p[i] == k​​，则有​​p[i + 1] == k + 1​​，得证。

p[i] != p[k]时

目前我们已经知道​​p[i] == p[k]​​​时​​next[i + 1]​​​的求法，当​​p[i] != p[k]​​时又该当如何？

从逻辑角度思考上面得到的结论：当​​p[i] == p[k]​​时，说明p[i]位置的字符可以归为前面已经匹配的子串，故当计算i + 1位置的k时，只需在原来k的基础上加1，表示在i + 1位置回退时只需回退到k的后一个位置即可。当p[i] != p[k]时，说明i + 1位置与之前已匹配的子串没有绝对的匹配关系，此时k应该继续回退，直到​​p[i] == p[k]​​或​​k == -1​​，然后根据p[i] == p[k]时的规律进行计算。

getNext()实现

有了上面的储备知识，我们就可以编写计算next数组的的代码。

/*
@param next next数组
@param sub 模式串
@param k 回退位置(next数组的数据)
@param i 遍历sub
*/
void KmpSolution::getNext(int*& next, string sub)
{
next[0] = -1;
int k = -1;//k一直是前一项(sub.at(i - 1))的k
for (int i = 1; i < sub.length(); )//注意这里i从 1 开始
    {
//p[i] == p[k]
if (k == -1 || sub.at(i - 1) == sub.at(k)){
next[i] = k + 1;
k++;//这种情况k应该自增1
i++;
        }
//p[i] != p[k]
else {
k = next[k];//继续回退
        }
    }
}

完整代码

void KmpSolution::getNext(int*& next, string sub)
{
next[0] = -1;
int k = -1;//k一直是前一项(sub.at(i - 1))的k
for (int i = 1; i < sub.length(); )
  {
if (k == -1 || sub.at(i - 1) == sub.at(k)){

next[i] = k + 1;
k++;//这种情况k应该自增1
i++;
    }
else {
k = next[k];
    }
  }
}

/*
@param str 主串
@param sub 模式串
@param i 遍历主串
@param j 遍历模式串
*/

int KmpSolution::KMP(string str, string sub)
{
int i = 0;
int j = 0;
int lenStr = str.length();
int lenSub = sub.length();
int* next = new int[lenSub];
getNext(next, sub);//计算next数组
while (i < lenStr && j < lenSub)
  {
if (j == -1 || str.at(i) == sub.at(j)){
i++;
j++;
    }
else {
j = next[j];
    }
  }
if (j == lenSub) {
return i - j;
  }
else {
return -1;
  }
}