字符串模式匹配——KMP算法

本周学习了第四章——字符串，其实，基本操作（查找、截取、连接、复制……）早在大一上C语言就已经学过了；而在大一下的C++中，string类也提供了很方便的库函数，所以，我们这节课的重点是KMP算法，这是我们目前课上学的第一个有难度的算法。

KMP算法确实有点“反常识”，导致它抽象而难于理解。我用这篇文章把自己理解的思想记录下来，辅以图解来直观记忆。这些图都是我用draw.io绘制的，转载请注明出处。

什么是KMP算法

KMP算法主要是字符串匹配问题的优化。

大部分时候，我们采用的字符串匹配都是O(n*m)的，也就是说，从头到尾遍历主串，以每个字符为开头尝试匹配，如果失配，就回溯到开头的下一个位置继续尝试，直到找到模式串或者遍历完主串。显然，最坏的情况是对主串的每一个位置，都可以部分匹配模式串而只差一个，比如在0000000000000000中找000001，此时，一共要进行n*m次比较。

然而，有这样的一种思路：在我们匹配了一段发现失配时，失配前的那一段是匹配的，也称主串和模式串部分匹配。在上面的例子中，我们匹配了前五个0之后，发现第六个1不匹配，如果按照朴素的方法，就是从s[1]开始重复此过程，然而，当i移动到1时，我们已经知道自此往后的五个都是0（是通过前面所说的的部分匹配得到的），那么我们可以直接比较第6位，如果是1，就匹配成功，否则就再将i向前移动一个。我作了个图，来体现匹配次数的差异。箭头指向的位置是需要判断的地方，可以推知，在这里，每次移动i，都仅仅需要多判断那个失配的位置而已，减少了大量的重复判断。

上面是有大部分一样字符的情况。这其实也是kmp算法最有优势的情况。那么，对于一般的情况，匹配过程又是怎么样的呢？

KMP算法的原理

不失一般性，作出下图。从主串的第一个橙色块开始，与模式串匹配，直到倒数第三个失配。同时，注意到，模式串中已匹配的部分，前面的红色块与后面的红色块相同，那么，容易推知，最后三个橙色块也与前面的红色块相同，如图所示。也就是说，在我们需要判断它们时，可以利用这个信息减少判断次数。

接下来，是最重要的一点。我在摸索的过程中，看了好几本教材的表述，以及很多的文章，很少有讲清楚这里的。大概是被算法中的i永远不回溯给限制住了。

这里，我将用和朴素的匹配方法类似的思想来解释KMP中神奇的操作。首先，我们先说说算法的目的：如果能在主串中找到模式串，就返回主串中第一次匹配成功的初始位置，否则返回-1。根据这个目标，当我们发现失配时，就将起始点移动到下一个可能匹配成功的位置，在朴素匹配中，也就是起始点的下一个位置。然而，依据上面的信息，我们可以把起始点移动地更远一些。那么，需要解决的问题就是：下一个可能起始点到底在哪！！！根据部分匹配的信息，我们可以得到可能的起始点必须满足的条件。请看图

在已知部分匹配的前提下，假如新的起始点在匹配过的内部，比如箭头所示位置，成功匹配的前提是满足如图红色的相等关系。可以看出，这就是匹配成功的部分的前缀和后缀相等的部分。那么，如果我们找到了最长的公共前后缀，不就也找到了下一个可能的起始点了嘛！此外，起始点确定后，中间部分也不用判断了（必然已经匹配），可以直接从失配的位置开始判断，体现在代码上就是主串的指针不回溯，而模式串的指针回溯到待匹配的位置（由于i-j就是起点，也就相当于右移了起点）。

所谓待匹配的位置又该怎么求呢？根据上面的分析，next[j]就应该是j前面最长公共前后缀的下一个位置。由于这个结果只与模式串有关，不管主串是什么，我们都可以把模式串在某处失配时应当跳到的位置求出来。所以，可以对模式串进行预处理，求出所有位置失配的下一跳，储存在一个next数组中。

如何求next数组呢？重申一下，next[i]应当是在i前面的序列的最长公共前后缀的后一个位置，比如说，abcabeabd，如果在e处失配，由于abcab的最长公共前后缀是ab，那么应该跳到c继续尝试匹配。我们可以用一种巧妙的方法求出next数组，也就是用模式串自身进行匹配，但是要注意主串从第二个位置开始尝试（之所以去掉第一个位置，是因为前后缀不能相同，否则会出现停在原地的情况，去掉第一个元素就保证了后缀不会是前缀），和上面的过程类似，具体步骤见下一节。

KMP代码解析

匹配部分的具体做法是：从头开始，正常匹配，i和j同步前进，当出现失配时，i不动，移动j到下一个待匹配的位置，继续上面的过程，直到匹配成功或者模式串的每个前缀都匹配不上i的位置，此时，称i完全失配，++i，从下一个位置开始重新匹配。可以写出匹配部分的代码如下。

s1=" "+s1;//添加头部哨兵，真正的字符串从i=1开始，作用在后面详述
s2=" "+s2;
int i=1,j=1;//初始从开头，也就是下标为1开始
while(i<s1.size()&&j<s2.size())//i到末端或j匹配成功，终止
{
    if(j==0||s1[i]==s2[j])//其中，s1[i]==s2[j]很好理解，就是当前位置匹配成功；而j==0就是i指向的位置完全失配，跳过当前位置
        ++i,++j;
    else//没有匹配成功，并且仍然有可能匹配，j跳到下一个位置尝试匹配（也就是上图的情况）
        j=next[j];
}
return j==s2.size()?i-j:-1;//判断结果，如果j==s2.size()，代表匹配成功，返回初始位置(i-j)，否则代表找不到，返回-1

求解next数组的具体做法是，先将next[1]=0，代表一个不能达到的位置，然后让i从1开始，j从0开始，进行匹配，正常匹配时，i和j同时步进，并记录下一个位置的next值（每次成功匹配，必然都是下一个位置的最长前后缀），如果当前位置完全失配，就将它的next置为1，也就是从头开始匹配。其余操作和上面匹配过程是一样的（毕竟求next数组也是在模式匹配嘛）。具体代码如下

vector<int> next(s2.size());//添加哨兵节点的过程省略
int i=1,j=0;//i从1开始，j从0开始
while(i<next.size()-1)//每次写入next的都是i+1，所以i<=next.size()-2
{
    if(j==0||s2[i]==s2[j])//正常匹配或者完全失配
        next[++i]=++j;//将下一个位置的next即为j的下一个位置（并步进i和j）
    else
        j=next[j];//可以想见，总是有j<i，所以next[j]是一定有的
}

next数组的求解要更难理解一点，所以用图解来表示一下具体步骤，仍是用abcabeabd举例，已添加了哨兵节点

最终的next数组就是[0 0 1 1 1 2 3 1 2 3]，其中next[0]=next[1]=0，是预先设定的。

如果还是有点不理解，可以自己试着写一个模式串推推看它的next数组，多想一想也就理解了。

最终代码

最后，以完整的KMP算法做结尾吧，写了这么多遍，背都背下来了😂😂

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    s1 = " " + s1; //在两个字符串前面添加哨兵，使真正的字符串从s[1]开始
    s2 = " " + s2;
    vector<int> next(s2.size()); //next数组
    next[1] = 0;
    int i = 1, j = 0;
    while (i < next.size() - 1) //生成next数组
        if (j == 0 || s2[i] == s2[j])
            next[++i] = ++j;
        else
            j = next[j];
    i = j = 1;
    while (i < s1.size() && j < s2.size())
        if (j == 0 || s1[i] == s2[j])
            ++i, ++j;
        else
            j = next[j];
    cout << (j == s2.size() ? i - j : -1) << endl;
    return 0;
}

这篇文章或许还不完善，如果我对KMP有了新的理解，一定会来更新。

10.2更新——KMP应用题

KMP看上去高深而又鸡肋，或许在字符串比较中能更快些(不过也是在n>>m时计算next数组的消耗才是值得的)，但在算法竞赛中似乎就显得很鸡肋了，毕竟自带的find库函数就绝对够用了。不过神奇的是，就在这周的周赛中，我用上了KMP。

是leetcode2430. 对字母串可执行的最大删除数，题目如下：

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：

删除 整个字符串 s ，或者
对于满足 1 <= i <= s.length / 2 的任意 i ，如果 s 中的前 i 个字母和接下来的 i 个字母相等，删除前 i 个字母。

例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s 的前两个字母和接下来的两个字母都等于 "ab" 。

返回删除 s 所需的最大操作数。

示例 1：

输入：s = "abcabcdabc"
输出：2
解释：
- 删除前 3 个字母（"abc"），因为它们和接下来 3 个字母相等。现在，s = "abcdabc"。
- 删除全部字母。
一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。
注意，在第二步操作中无法再次删除 "abc" ，因为 "abc" 的下一次出现并不是位于接下来的 3 个字母。

示例 2：

输入：s = "aaabaab"
输出：4
解释：
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "aabaab"。
- 删除前 3 个字母（"aab"），因为它们和接下来 3 个字母相等。现在，s = "aab"。 
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "ab"。
- 删除全部字母。
一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。

示例 3：

输入：s = "aaaaa"
输出：5
解释：在每一步操作中，都可以仅删除 s 的第一个字母。

提示：

1 <= s.length <= 4000
s 仅由小写英文字母组成

这类题，应该很容易想到动态规划或者记忆化搜索。也就是说，对于删除过程中产生的每一个字符串，我们都找到所有可能的删除点，然后执行操作。用记搜或者DP找出最大值。由于删除操作删除的一定是前缀，过程中最多产生s.size()个字符串，这是O(N)。再考虑对每个字符串操作的复杂度，可以看到，s.length最大可以到4000，这意味着最多容许O(N^2)的时间复杂度，也就是说，每个字符串找删除点的过程，必须是O(N)的。

考虑找删除点的过程。朴素的思路是遍历前缀，并逐个判断它和后面size长度的字符串是否相等。可是，这样不断切片比较的复杂度是O(N^2)，不符合O(N)的要求。而KMP算法可以帮助我们在O(N)的时间复杂度内找到所有删除点。我们只需要善用next数组。

举个例子，考虑aabaab的删除点：可以删掉第一个a，也可以删掉aab。而第二种删除方案，实际上也可以视为前缀相继出现了两次。也就是说，基于next数组的意义——最长公共前后缀，如果最长公共前后缀恰好相连，不就是前缀相继出现了两次嘛。那么，映射到next数组上，也就是j=2next[j]，就可以从next[j]开始截取。(这里采用的是不添加哨兵的方法，添加哨兵只需拿这个例子推一下)。需要注意的是，我们得在最后添加空格，使整个字符串都被遍历到。

我们求出它的next数组和截取位置如图

由于求next数组是O(N)的，所以求删除点也是O(N)的，这就满足了要求。

接着，可以利用DP和记搜分别写出代码，以长度为键即可。

记忆化搜索代码

//记忆化搜索+KMP求删除点
class Solution {
public:
    int ans=0;
    vector<int> memo;//记搜
    void search(string &s,int cnt)
    {
        if(memo[s.size()-1]>=cnt)
            return ;
        memo[s.size()-1]=cnt;
        vector<int> next(s.size());
        next[0] = -1;
        int i = 0, j = -1;
        while (i < next.size() - 1)
        {
            if (j == -1 || s[i] == s[j])
                next[++i] = ++j;
            else
                j = next[j];
        }
        bool flag=true;
        for(int k=0;k<next.size();++k)
            if(2*next[k]==k)//找到所有删除点
            {
                flag=false;
                string tmp=s.substr(next[k]);
                search(tmp,cnt+1);
            }
        if(flag)//没有满足条件二的删除点，全部删除，用一次
            ans=max(ans,cnt+1);
    }
    int deleteString(string s) {
        memo=vector<int> (s.size()+1,-1);
        s+=" ";//最后加上空格，为了全部遍历
        search(s,0);
        return ans;
    }
};

动态规划代码

//KMP求删除点+DP
class Solution {
public:
    int deleteString(string s) {
        vector<int> memo(s.size()+1,1);
        string now=" ";
        for(int pos=s.size()-1;pos>=0;--pos)
        {
            now=s[pos]+now;
            vector<int> next(now.size());
            next[0] = -1;
            int i = 0, j = -1;
            while (i < next.size() - 1)
            {
                if (j == -1 || now[i] == now[j])
                    next[++i] = ++j;
                else
                    j = next[j];
            }
            for(int k=0;k<next.size();++k)
                if(2*next[k]==k)//找到所有删除点
                    memo[now.size()-1]=max(memo[now.size()-1],memo[now.size()-next[k]-1]+1);
        }
        return memo[s.size()];
    }
};

10.7更新

新遇到的KMP练习题