【算法-字符串3】听说KMP很难？进来看这篇：实现strstr()，查找子串

今天，带来KMP算法的讲解。文中不足错漏之处望请斧正！

理论基础点这里

---

今天我们来实现strstr()。

题意转化

在一个字符串mainStr中找另一个字符串subStr。

解决思路

• 两指针i和j分别在mainStr和subStr中拿取字符尝试匹配
  • 匹配：继续
  • 不匹配：
    • 暴力：i 回退，两串从头开始匹配 O(n*m)
    • KMP：i 不回退，两串从前面仍然匹配的位置继续匹配

暴力算法效率太低，一旦有不匹配的字符，i要回退到这次匹配的 i 的起始位置的下一个位置；j 要回退到子串起始位置。

更优的算法是KMP算法。

KMP算法

KMP是一种线性时间复杂度的字符串匹配算法，通过减少 i 和 j 的回退来提高效率。

算法思路如下：

• 两指针 i 和 j 分别在 mainStr 和 subStr 中拿取字符尝试匹配
  • 匹配：两串的指针继续后移
  • 不匹配：两串的指针移动到 下次匹配时两串仍然匹配的部分 后面，准备进行下一次尝试匹配
  • j == subStr.size() 表示匹配成功

关于“仍然匹配的部分”，等会讲解，现在先看过程。

图中，两串已经进行了5个字符的匹配，在尝试匹配第6个时发现不匹配：KMP会两串的指针移动到 下次匹配时两串仍然匹配的部分 后面，继续尝试匹配。

怎么计算仍然匹配的部分

利用subStr已匹配部分的最长相等前后缀进行等量代换，找下次匹配两串仍然匹配的部分。

对于下图：

有：

1. subStr的前缀aa == subStr的后缀aa （最长相等前后缀）
2. subStr的前缀aa == mainStr的前缀aa （两串的这一部分已匹配）
3. subStr的后缀aa == mainStr的后缀aa （两串的这一部分已匹配）

可得：

图中红色部分全部相等。

即：

mainStr后缀aa == subStr前缀aa，它们其实就是 下次匹配仍然匹配的部分。可以对照图仔细理解。

为什么要用最长的相等前后缀长度？

因为要尽可能利用已匹配字符来减少 j 的回退，毕竟能只退一步为什么要退两步？

那，如何获取最长相等前后缀长度？这就要引入next表了。

为什么用最长相等前后缀就能优化效率？

本质上，我们是利用 ”已匹配字符“ 来优化效率，最长相等前后缀只是我们优化的一种途径。最长相等前后缀利用已匹配字符的对称性，加上已匹配字符，代换出了 若排除不匹配字符，下一次尝试匹配还会有哪些部分仍然匹配。

大家好好把这个问题想明白，能很大程度帮助理解KMP，很多文章视频没有讲到这一点。

如何获取最长相等前后缀长度

要进行字符串匹配，两串在任意一个字符尝试匹配时都可能失败，那按照上面的说法，对于某字符串 str 的所有部分（也就是以任一字符结尾的子串），我们都需要计算它的最长相等前后缀长度。

并且，由于这个长度决定了 j 下一步如何回退，所以我们称存储 str 所有部分最长相等前后缀长度的表为 next表。

步骤如下：

1. 两个指针 len 和 i 分别指向 前缀的末尾 和 后缀的末尾（len是前缀末尾的指针，+1就是前缀长度）
2. 用 i 遍历 str，len 和 i 每次都要为 i 结尾的后缀找一个最长相等前缀

   1. 当前后缀末尾不等：前缀前面部分 + 前缀末尾 != 后缀前面部分 + 后缀末尾
      无法直接形成新的最长相等前后缀，所以我们退而求其次，让 len 回退，找更短的前缀，尝试和当前后缀匹配
      
      解释：

      1. b前的a == c前的a 已匹配，是相同的（利用已匹配的字符等量代换）
      2. 对照 c前的a的最长相等前后缀长度，可知 subStr第一个a == c前的a
      3. 所以三者相等
      4. ac 无法匹配 ab，那根据 ac 中的a向前找到其最长相等前后缀 a，让len回退到next[len - 1]，继续尝试匹配。回退是为了往回找更短的前缀，尝试匹配。

   2. 当前后缀末尾相等：前缀前面部分 + 前缀末尾 == 后缀前面部分 + 后缀末尾
      可以直接形成新的最长相等前后缀，++len，收获长度
      

优化在哪了

• i 不需要回退，减少整体匹配的次数
• j 按策略回退，不用每次都匹配所有字符

总结思路

1. 获取next表
2. i 和 j 分别在 mainStr 和 subStr 中取字符尝试匹配
   1. 匹配：两串的指针继续后移
   2. 不匹配：两指针移动到下次匹配时，两串仍然匹配的部分后面
      1. 下次匹配时，有仍然匹配的部分：利用最长相等前后缀长度等量代换，找到下一次匹配仍然匹配的部分
      2. 下次匹配时，无仍然匹配的部分：没有优化空间，i后移，j置零，两串都回退，重新开始匹配
      3. 当 j == subStr.size() 表示匹配成功
3. 跳出还没匹配成功，表示失败，返回-1

编程实现

class Solution {
public:
    int strStr(string mainStr, string subStr) {
        vector<int> next = getNext(subStr); // 获取next表
        int i = 0;
        int j = 0;
        
        while (i < mainStr.size()) { // i 和 j 分别在 mainStr 和 subStr 中取字符尝试匹配
            if (mainStr[i] == subStr[j]) { // 匹配：两串的指针继续后移
                ++i;
                ++j;
            } else { // 不匹配：指针移动到下次匹配时，两串仍然匹配的部分后面
                if (j > 0) { // 下次匹配时，有仍然匹配的部分
                    j = next[j - 1];
                } else { // 下次匹配时，无仍然匹配的部分
                    ++i;
                    j = 0;
                }
            }

            if (j == subStr.size()) {
                return i - j;
            }
        }

        return -1;
    }

private:
    vector<int> getNext(const string &str) {
        vector<int> next(str.size());
        int len = 0;
        int i = 1;

        next[0] = 0;

        while (i < str.size()) {
            while (len > 0 && str[i] != str[len]) { // len > 0 避免越界
                len = next[len - 1];
            }

            if (str[i] == str[len]) {
                ++len; // len指向前缀末尾，++就是前缀长度
            }

            next[i++] = len; // 收获当前的后缀的最长前后缀长度
        }

        return next;
    }
};

• 时间复杂度: O(n + m)
• 空间复杂度: O(m)，next数组

---

今天的分享就到这里了，感谢您能看到这里。

这里是培根的blog，期待与你共同进步！