KMP算法

• KMP算法是一种改进的字符串匹配算法，是由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此叫做KMP算法。
• KMP算法的核心就是利用匹配失败后的信息，尽量减少模式串与文本串的匹配次数，以达到快速匹配的目的。

说明一下： 如果要在字符串a中寻找字符串b第一次出现的位置，那么字符串a就叫做文本串，而字符串b叫做模式串。

KMP算法的核心思想

KMP算法的核心思想

下面通过抽象图来讲解KMP算法的核心思想，文本串和模式串的长度分别为 $n$ 和 $m$ 。如下：

假设现在正在以文本串中下标为 $s$ 的字符开始与模式串进行匹配，并且已经匹配到了模式串中下标为 $j$ 的字符，即文本串中的子串 $[s,i]$与模式串中的子串 $[0,j]$ 相同。如下：

在继续比较后续字符的时候，如果文本串中的第 $i+1$ 个字符与模式串中的第 $j+1$ 个字符相同，就让指向文本串和指向模式串的指针同时向后移动即可。如下：

但在比较后续字符的过程中，如果发现文本串的第 $i+1$ 个字符与模式串的第 $j+1$ 个字符不相同，此时说明以文本串中下标为 $s$ 的字符开始无法匹配成功。如下：

这时最简单的做法就是，以文本串中下标为 $s+1$ 的字符开始重新尝试与模式串进行匹配，这意味着指向文本串的指针和指向模式串的指针都需要进行回退。如下：

但在KMP算法中并不是这样做的，对于文本串来说，如果在 $(s,i]$ 这个下标范围内有一个下标 $k$ ，使得以文本串中下标为 $k$ 的字符开始能够与模式串成功匹配，即文本串中的子串 $[k,k+m-1]$ 与模式串相同。如下：

因为文本串中的子串 $[k,k+m-1]$ 与模式串相同，所以文本串中的子串 $[k,i]$ 与模式串中的子串 $[0,x]$ 相同，其中 $x-0+1=i-k+1$，即这两个子串的长度相同。如下：

除此之外，因为文本串中的子串 $[s,i]$ 与模式串中的子串 $[0,j]$ 相同，所以文本串中的子串 $[k,i]$ 又与模式串中的子串 $[y,j]$ 相同，其中 $j-y+1=i-k+1$，即这两个子串的长度相同。如下：

所以模式串中的子串 $[0,x]$ 与子串 $[y,j]$ 相同，而这两个子串就是模式串中的子串 $[0,j]$ 的一对相同前后缀，因此如果存在上述所说的下标 $k$ 那么子串 $[0,j]$ 就一定存在相同前后缀，此时模式串中的指针只需要回退到前缀的下一个位置继续进行匹配即可，而文本串中的指针不需要回退。

示意图如下：

KMP算法的核心思想：

• 在文本串与模式串匹配的过程中，指向文本串的指针不需要回退，指向模式串的指针只需要在字符匹配失败的时候适当回退即可，不一定会回退到模式串的开头。
• 当文本串中的第 $i+1$ 个字符与模式串中的第 $j+1$ 个字符匹配失败时，如果模式串的子串 $[0,j]$ 存在最长相同前后缀，则直接让指向模式串的指针回退到对应前缀的下一个位置继续进行匹配即可。
• 当字符匹配失败时，如果模式串的子串 $[0,j]$ 不存在相同前后缀，则说明在文本串的 $(s,i]$ 下标范围内不存在所谓的下标 $k$ ，这时让指向模式串的指针回退到模式串的开头即可。

说明一下：

• 因为在进行字符串匹配时，是要在文本串中找到模式串第一次出现的位置，所以要让上图中的下标 $k$ 尽量靠前，也就是要让 $[k,i]$ 、$[0,x]$ 和 $[y,j]$ 这三个子串的长度尽可能长，所以当出现字符匹配失败时，需要找到子串的 $[0,j]$ 的最长相同前后缀。
• 当字符匹配失败时，说明以下标为 $s$ 的位置开始匹配无法匹配成功，因此下标 $k$ 的取值范围是 $(s,i]$ ，所以 $[k,i]$ 的长度必须小于子串 $[s,i]$的长度。
• 子串 $[0,x]$ 和 $[y,j]$ 的长度和 $[k,i]$ 是相同的，子串 $[0,j]$ 的长度和 $[s,i]$ 是相同的，因此子串 $[0,x]$ 和 $[y,j]$ 的长度就必须小于子串 $[0,j]$ 的长度，虽然我们要的是子串 $[0,j]$ 的最长相同前后缀，但是这个前后缀的长度必须小于子串 $[0,j]$ 的长度，所以在KMP算法中，对于只有一个字符的字符串来说，它没有最长相同前后缀。

KMP算法的前缀表

KMP算法的前缀表

• 在文本串与模式串匹配的过程中，如果文本串中的第 $i+1$ 个字符与模式串中的第 $j+1$ 个字符匹配失败，那么就需要根据模式串的子串 $[0,j]$ 的最长相同前后缀，来判断应该让指向模式串的指针回退到哪个位置。
• 在匹配模式串中的任意一个字符时，都有可能会出现匹配失败的问题，因此在进行字符串匹配之前，我们需要提前找出以模式串中每一个字符为结尾的子串的最长相同前后缀，以供后续字符串匹配时使用。
• 由于字符串中的字符下标是从0开始的，因此模式串中的子串 $[0,j]$ 的最长相同前后缀的前缀的下一个位置的下标值，实际就是最长相同前后缀的长度，所以只需要计算出以模式串中的每一个字符为结尾的最长相同前后缀的长度即可。
• KMP算法中的前缀表的长度与模式串的长度相同，其中前缀表中的第 $i$ 个位置，记录的就是模式串中的子串 $[0,i]$ 的最长相同前后缀的长度。

生成前缀表的过程

下面通过抽象图来讲解KMP算法中生成前缀表的过程，模式串的长度为 $m$ 。如下：

假设以下标为 $i$ 的字符结尾的子串的最长相同前后缀是子串 $[0,x]$ 和 $[y,i]$ ，如果这个最长相同前后缀的长度为 $j$ ，那么前缀的下一个位置的下标就是 $j$ 。如下：

如果模式串中下标为 $i+1$ 的字符与下标为 $j$ 的字符相同，那么以下标为 $i+1$ 的字符结尾的子串的最长相同前后缀就是子串 $[0,j]$ 和 $[y,i+1]$ ，其长度为 $j+1$ ，所以前缀的下一个位置的下标就是 $j+1$ 。如下：

但如果模式串中下标为 $i+1$ 的字符与下标为 $j$ 的字符不相同，此时说明以下标为 $i+1$ 的字符结尾的子串的最长相同前后缀的长度小于 $j+1$ 。如下：

假设在 $(y,i]$ 这个下标范围内有一个下标 $k$ ，使得子串 $[k,i+1]$ 能够成为子串 $[0,i+1]$ 的最长相同前后缀中的后缀，即子串 $[0,a+1]$ 与子串 $[k,i+1]$ 相同，其中 $a+1-0+1=i+1-k+1$ ，即这两个子串长度相同。如下：

因为子串 $[0,a+1]$ 与子串 $[k,i+1]$ 相同，所以子串 $[0,a]$ 与子串 $[k,i]$ 相同，其中 $a-0+1=i-k+1$ ，即这两个子串的长度相同。如下：

除此之外，因为子串 $[0,x]$ 与子串 $[y,i]$ 相同，所以子串 $[b,x]$ 与子串 $[k,i]$ 相同，其中 $x-b+1=i-k+1$ ，即这两个子串的长度相同。如下：

所以子串 $[0,a]$ 与子串 $[b,x]$ 相同，而这两个子串就是子串 $[0,x]$ 的一对相同前后缀。因此如果存在上述所说的下标 $k$ ，那么子串 $[0,i]$ 的最长相同前后缀的前缀 $[0,x]$ 就一定存在相同前后缀，此时让指向前缀的指针回退到子串 $[0,x]$ 的最长相同前后缀的前缀的下一个位置继续进行匹配即可，而指向后缀的指针不需要回退。

示意图如下：

KMP算法的前缀表：

• 在生成前缀表的过程中，指向后缀的指针不需要回退，指向前缀的指针只需要在字符比较失败的时候适当回退即可，不一定会回退到字符串开头。
• 当第 $i+1$ 个字符（后缀的下一个字符）与第 $j$ 个字符（前缀的下一个字符）不相同时，如果子串 $[0,j-1]$ 存在最长相同前后缀，则直接让指向前缀的指针回退到对应前缀的下一个位置继续进行匹配即可。
• 当字符比较失败时，如果子串 $[0,j-1]$ 不存在相同前后缀，则说明在 $(y,i]$ 下标范围内不存在所谓的下标 $k$ ，这时让指向前缀的指针回退到模式串的开头即可。

说明一下：

• 因为在生成前缀表时，是要找到以每个字符为结尾的子串的最长相同前后缀，所以要让上图中的下标 $k$ 尽量靠前，也就是要让 $[k,i]$ 、$[0,a]$ 和 $[b,x]$ 这三个子串的长度尽可能长，所以当出现字符比较失败时，需要找到子串 $[0,j-1]$ 的最长相同前后缀。
• 当字符比较失败时，说明图中子串 $[y,i+1]$ 无法作为子串 $[0,i+1]$ 的相同前后缀，因此下标 $k$ 的取值范围是 $(y,i]$ ，所以 $[k,i]$ 的长度必须小于 $[y,i]$ 的长度。
• 子串 $[0,a]$ 和 $[b,x]$ 的长度和 $[k,i]$ 是相同的，子串 $[0,x]$ 的长度和 $[y,i]$ 是相同的，因此子串 $[0,a]$ 和 $[b,x]$ 的长度就必须小于子串 $[0,x]$ 的长度，虽然我们要的是子串 $[0,j-1]$ 的最长相同前后缀，但是这个前后缀的长度必须小于子串 $[0,j-1]$ 的长度。（$j-1$ 与 $x$ 相同）
• 仔细想想，你会发现生成前缀表的过程和前面字符串匹配的过程是类似的，生成前缀表时指向前缀的指针和字符串匹配时指向模式串的指针的行为是一样的，当出现字符串匹配失败时，指向模式串的指针会回退，而当出现字符比较失败时，指向前缀的指针会回退。

KMP算法的实现

根据模式串生成前缀表

生成前缀表的逻辑如下：

• 将以下标为0的字符结尾的子串的最长相同前后缀长度初始化为0，因为在KMP算法中只有单个字符的字符串没有相同前后缀，因此其最长相同前后缀的长度为0。
• 用指针 $i$ 指向后缀的下一个位置，指针 $j$ 指向前缀的下一个位置。在计算以下标为 $i$ 的字符结尾的子串的最长相同前后缀的长度时，如果下标为 $j$ 的字符与下标为 $i$ 的字符不相同，那么指针 $j$ 回退到子串 $[0,j-1]$ 的最长相同前后缀的前缀的下一个位置，如果字符仍然与指针 $i$ 指向的字符不相同，则指针 $j$ 继续回退，直到与指针 $i$ 指向的字符相同或回退到字符串开头。
• 如果下标为 $j$ 的字符与下标为 $i$ 的字符相同，则指针 $j$ 后移，此时指针 $j$ 指向的就是子串 $[0,i]$ 的最长相同前后缀的前缀的下一个位置，也就是最长相同前后缀的长度。

代码如下：

//根据模式串生成前缀表
vector<int> getNext(const string& needle) {
    
    //j: 指向前缀末尾位置（前缀的长度）
    //i: 指向后缀末尾位置
    int n = needle.size();
    vector<int> next(n);
    next[0] = 0; //以下标为0的字符结尾的字符串的相同前后缀长度为0
    int j = 0; //指向前缀末尾位置
    for (int i = 1; i < n; i++) {
     //i从1开始,next[0]已被初始化
        while (j > 0 && needle[j] != needle[i]) {
     //前后缀末尾不相同,前缀位置向前回退
            j = next[j - 1]; //j回退到以下标为j-1的字符结尾的字符串的最长相同前后缀的前缀的下一个位置
        }
        if (needle[j] == needle[i]) {
     //前后缀末尾相同
            j++; //j后移后的数值就是此时前缀的长度
        }
        next[i] = j; //以下标为i的字符结尾的字符串的相同前后缀的长度（也是前缀的下一个位置的下标）
    }
    return next; //返回前缀表
}

使用前缀表进行字符串匹配

字符串匹配的逻辑如下：

• 如果模式串为空串，那么模式串在文本串中第一次出现的位置就是第0个位置，否则需要进行字符串匹配，在进行字符串匹配之前，需要先根据模式串生成前缀表。
• 用指针 $i$ 指向文本串中下一个待比较的字符，指针 $j$ 指向模式串中下一个待比较的字符。在字符串匹配过程中，如果文本串中下标为 $i$ 的字符与模式串中下标为 $j$ 的字符不匹配，那么指针 $j$ 回退到子串 $[0,j-1]$ 的最长相同前后缀的前缀的下一个位置，如果字符仍然与指针 $i$ 指向的字符不匹配，则指针 $j$ 继续回退，直到与指针 $i$ 指向的字符相同或回退到模式串开头。
• 如果模式串中下标为 $j$ 的字符与文本串中下标为 $i$ 的字符匹配，则指针 $j$ 后移，如果指针 $j$ 移到了模式串末尾，则匹配完毕，此时文本串中的起始匹配位置即为模式串第一次出现的位置。

代码如下：

int searchNeedle(string haystack, string needle) {
    
    //j: 指向模式串中下一个待比较的字符
    //i: 指向文本串中下一个待比较的字符
    int n = needle.size();
    if (n == 0) //模式串为空串
        return 0;
    vector<int> next = getNext(needle); //根据模式串生成前缀表
    int j = 0; //指向模式串中下一个待比较的字符
    for (int i = 0; i < haystack.size(); i++) {
     //指向文本串中下一个待比较的字符
        while (j > 0 && needle[j] != haystack[i]) {
     //当前字符不匹配,指向模式串的指针向前回退（重新寻找匹配位置）
            j = next[j - 1]; //回退到以下标为j-1的字符结尾的字符串的最长相同前后缀的前缀的下一个位置
        }
        if (needle[j] == haystack[i]) {
     //当前字符匹配
            j++; //指向模式串的指针后移
            if (j == n) //j已经到达模式串末尾,匹配完毕
                return i - n + 1; //返回文本串中的起始匹配下标
        }
    }
    return -1; //匹配失败,文本串中没有出现过模式串
}

KMP算法的时间复杂度

KMP算法的时间复杂度

假设文本串长度为 $n$ ，模式串长度为 $m$ ：

• 对于暴力解法来说，它会依次选取文本串中的每一个字符作为匹配的起始位置，如果当前起始位置匹配失败则尝试下一个起始位置重新从模式串的开头进行匹配，因此暴力解法的时间复杂度是 $O(n\times m)$ 。
• 对于KMP算法来说，它会先遍历一遍模式串生成前缀表，然后再遍历一遍文本串进行字符串匹配，因此KMP算法的时间复杂度是 $O(n+m)$ 。