KMP

KMP算法用于字符串匹配优化

假设主串S长度为n， 模式串P长度为m

暴力做法，时间复杂度为${O(n * m)}$

// 暴力匹配
int i = 0, j = 0;
while (i < s.length())
{
    if (s[i] == p[j])
        ++i, ++j;
    else
        i = i - j + 1, j = 0;
    if (j == p.length())  // 匹配成功
    {
        // 对s[i - j .. i - 1]进行一些操作
        cout << i - j << endl;
        i = i - j + 1;
        j = 0;
    }
}

KMP

kmp算法的思想是，sh去预处理模板串 nxt[i] = j

$nxt[i]$的含义：对于字符串的前缀子串$S[0, i - 1]$，$nxt[i]$是该前缀子串所有相等的前后缀里长度的最大值。

举个例子，假设模式串为"ABABC"，nxt[] = [-1, 0, 0, 1, 2]
nxt[0] = -1，因为在0位置之前没有字符串，所以不存在相等的前缀和后缀。
nxt[1] = 0， 因为在1位置之前的字符串为"A"，其相等的前缀和后缀长度为0(真前缀，要小于S[0,i - 1]长度)。
nxt[2] = 0， 因为在2位置之前的字符串为"AB"，其相等的前缀和后缀长度为0。
nxt[3] = 0， 因为在3位置之前的字符串为"ABA"，其相等的前缀和后缀长度为1。
nxt[4] = 0， 因为在4位置之前的字符串为"ABAB"，其相等的前缀和后缀长度为2。

有了nxt数组之后，KMP算法可以避免在匹配过程中对模式串进行无效的回溯，从而提高匹配的效率。具体而言，当匹配到文本串中的某个位置i和模式串中的某个位置j不匹配时，我们可以根据nxt[j]的值将模式串向右移动j - nxt[j]个字符，从而避免了匹配中出现无效的回溯.

nxt[i] = j记录的就是当前以i作为后缀末位时，j对应的前缀末位的位置，有使得${p[1, j] == p[i - j + 1, i]}$，这两段前后缀字符串相等，并且不难发现j就是模式串可移动的长度。

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

string s; // 主串s
string p; // 模式串p

vector<int> get_next(string& p) {
    int m = p.size();
    
    vector<int> nxt(m);
    nxt[0] = -1;
    for (int i = 1, j = -1; i < m; i ++) {
        while (~j && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j ++;

        nxt[i] = j;
    }
    
    return nxt;
}

vector<int> kmp(string& s, string& p) {
    int n = s.size();
    int m = p.size();
    
    vector<int> res;
    vector<int> nxt = get_next(p);
    for (int i = 0, j = -1; i < n; i ++) {
        while (~j && s[i] != p[j + 1]) j = nxt[j];
        if (s[i] == p[j + 1]) j ++;

        if (j == m - 1) {
            // 匹配成功
            res.emplace_back(i - m + 1);  // 匹配成功时，p在s的起始下标
            j = nxt[j];
        }
    }
    
    return res;
}

int main() { 
    cin >> s; cin >> p;
    
    vector<int> res = kmp(s, p);

    for(auto& r : res) printf("%d ", r);

    return 0;
}

复杂度分析

• 时间复杂度：$O(2m + 2n)$ 。

  分析:

  1. 对于求nxt数组的过程

  外层for循环每当i++，j最多跟着一起++，所以 j 最多 + m次;
  内层while循环，j 肯定是 >= 0的，j最大为m，所以也最多要-m次; 因此while循环整个过程最多执行m次

  2. 对于kmp匹配的过程，同理

  外层for循环每当i ，j最多跟着一起，所以 j 最多 +n次;
  内层while循环，j 肯定是 >= 0的，j最大为n，所以也最多要 - n次; 因此while循环整个过程最多执行n次

  所以总共是2m + 2n

• 空间复杂度：$O(n)$，主要是$nxt$和$res$数组占用$O(n)$空间。

练习eg:

ACwing-831.KMP字符串

应用：循环节

$nxt[i]$的含义：对于字符串的前缀子串$S[0, i]$，$nxt[i]$是该前缀子串所有相等的前后缀里长度的最大值。

令$T = n - nxt[n]$，则$T$是最小循环节，并且如果$T\nmid n$，则题目无解。

证明1：$T$是一个最小循环节。

反证法：假设$\exists T' < T$，
那么有$n - T' > n - T = nxt[n]$，与$nxt[n]$是所有相等的前后缀里长度的最大值这一点矛盾。

证明2：如果字符串中存在更大的循环节$T'$，则$T'$必然是$T$的整数倍，即$T \mid T'$。

反证法：假设$\exists T' > T$，且$T \nmid T'$,
那么设$d = gcd(T, T')$，易知$d \mid T$，因此$d < T$。
由裴蜀定理，可知$d = xT + yT'$成立，不妨假设$x > 0, y < 0$，那么对于原字符串$S$：
$\forall i\in n, S_i = S_{i + T} = S_{i + 2 T} = ... S_i+xT = S_{i + xT -T'} = S_{i + xT - 2T'} = S_{i + xT - yT'} = s_{i + d}$
得到$S_i = S_{i + d}$，由定义可知$d$是一个循环节，又因为$d < T$，与$T$是最小循环节矛盾。

练习eg:

Acwing-141.周期

最小表示法