S-L19 字符串算法¶

#include <bits/stdc++.h>
using namespace std;

// KMP：next 数组（失配指针），nx[i] = s[0..i] 的最长相等真前后缀长度 - 1
vector<int> next_array(const string& s) {
    int n = (int)s.size();
    vector<int> nx(n, -1);
    for (int i = 1; i < n; i++) {
        int j = nx[i - 1];
        while (j != -1 && s[i] != s[j + 1]) j = nx[j];
        if (s[i] == s[j + 1]) j++;
        nx[i] = j;
    }
    return nx;
}

// 返回 pattern 在 text 中所有出现位置（0-based）；分隔符需不在两串中出现
vector<int> kmp_search(const string& text, const string& pattern) {
    string s = pattern + "#" + text;
    auto nx = next_array(s);
    vector<int> res;
    int m = (int)pattern.size();
    for (int i = m + 1; i < (int)s.size(); i++)
        if (nx[i] == m - 1) res.push_back(i - 2 * m);
    return res;
}