学学字符串的匹配算法，例如单模式串匹配的 KMP 算法和 Sunday 算法；多模式串 TODO。

单模式串匹配

KMP 算法

KMP 算法对模式串 p 进行了预处理，计算出 next 数组。在每次失配发生时，不回退文本串里的指针 i，而是根据 next 数组中模式串失配位置 j 的前一个位置的值 next[j - 1] 决定模式串可以向右移动的次数。如下图所示：

可以发现在前 j-1 的模式子串 ABCAB 中拥有相同前后缀 AB，那么失配后下次的比较就能跳过对前缀 AB 的比较，从而节省一定的时间。因此 next[j] 的含义就是：记录下标 j 之前（包括 j）的模式串 p 中，最长相等前后缀的长度。

可以通过递推的方式构造 next 数组：

1. 将模式串 p 拆分成 left 和 right 两部分。left 表示前缀串开始所在的位置，right 表示后缀串开始所在的位置。起始 left = 0, right = 1。
2. 比较 p[left] 是否和 p[right] 相等：
   1. p[left] == p[right]：前后缀相同，让 left += 1，此时 left 既是前缀下一次比较的位置，又是当前最长相同前后缀的长度。
   2. p[left] != p[right]：前后缀不相同，让后缀开始位置 k 不动，前缀 left 不断回退 next[left - 1]，直至 p[left] == p[right]。
3. 记录下标 right 之前的模式串 p 中，最长相同前后缀的长度为 left。即 next[right] = left。

代码如下：

vector<int> GenerateNext(const std::string& pattern)
{
    int n = pattern.length();
    vector<int> next(n);
    
    int left = 0;
    for (int right = 1; right < n; ++right)
    {
        // 匹配不成功就让left一直回退next[left - 1]
        while (left > 0 && pattern[left] != pattern[right])
        {
            left = next[left - 1];
        }
        
        // 匹配成功就让left+1
        if (pattern[left] == pattern[right])
        {
            left++;
        }
        
        // 更新next[right]
        next[right] = left;
    }
    
    return next;
}

有了 next 数组后，便能进行比较了，KMP 算法的步骤如下：

1. 求 next 数组；
2. 用 i, j 两个指针进行比较，i 遍历文本串，j 遍历模式串；
3. 判断 t[i] 和 p[j] 是否相同：
   1. 不相同，一直回退模式串 j = next[j - 1]，直至 j == 0 或者前缀比较成功。
   2. 相同，如果是部分匹配成功，就让 j 和 i 继续匹配下去；如果是全部匹配成功，就返回匹配成功的开始位置 i - j + 1。
4. 如果从未完全匹配成功，说明匹配失败。

代码如下：

int kmp(const string& target, const string& pattern)
{
    vector<int> next = GenerateNext(pattern);
    for (int i = 0, j = 0; i < target.length() ++i)
    {
        // 匹配不成功, 就一直回退
        while (j > 0 && target[i] != pattern[j])
        {
            j = next[j - 1];
        }
        // 部分匹配成功, 继续
        if (target[i] == pattern[j])
        {
            j++;
        }
        // 完全匹配成功, 返回匹配开始位置
        if (j == pattern.length())
        {
            return i - j + 1;
        }
    }
    
    // 匹配失败
    return -1;
}

KMP 算法的时间复杂度是 O(m + n)，时间花费在构造 next 数组和遍历文本串上了。

Sunday 算法

TODO

多模式串匹配

TODO

参考资料

• 算法通关手册（LeetCode） | 算法通关手册（LeetCode） (itcharge.cn)