字符串匹配

KMP 算法

KMP 通过预处理失配函数 fail[]（也叫 next[]）避免匹配失败时的回退。fail[i] = pattern[0..i] 的最长真前缀且等于后缀的长度。失配时 j 跳回 fail[j-1]，文本指针 i 不后退，总时间 O(n+m)。

关键步骤

1. 预处理：用双指针构建 fail[] 数组（O(m)）
2. 匹配：维护 j（模式已匹配长度），失配时 j = fail[j-1]
3. j == m 时找到完整匹配，记录位置后 j = fail[j-1] 继续

// KMP: find all occurrences of pattern in text — O(n+m)
vector<int> kmpSearch(const string& text, const string& pat) {
    string s = pat + "#" + text;
    int n = s.size(), m = pat.size();
    vector<int> fail(n, 0);
    // Build failure function
    for (int i = 1; i < n; i++) {
        int j = fail[i - 1];
        while (j > 0 && s[i] != s[j]) j = fail[j - 1];
        if (s[i] == s[j]) j++;
        fail[i] = j;
    }
    // Positions where fail[i] == m (0-indexed start in text)
    vector<int> res;
    for (int i = m + 1; i < n; i++)
        if (fail[i] == m) res.push_back(i - 2 * m); // convert to text index
    return res;
}

典型题目

• 28. 找出字符串中第一个匹配项的下标（KMP 基础）
• 459. 重复的子字符串（fail[m-1] 能整除 m 且 m % (m-fail[m-1]) == 0）
• 214. 最短回文串（在 s + '#' + reverse(s) 上跑 KMP）

fail[] 语义：fail[i] 表示 pattern[0..i] 中最长的「真前缀 = 后缀」的长度，不是跳转目标下标，失配时应跳到 fail[j-1]（j > 0 时）。

Rabin-Karp（滚动哈希）

滚动哈希将字符串映射为多项式哈希，在 O(1) 内计算滑动窗口哈希：hash(s[l+1..r+1]) = (hash(s[l..r]) - s[l]*BASE^(r-l)) * BASE + s[r+1]。哈希碰撞概率 O(1/MOD)，可用双哈希进一步降低。

// Rolling hash — find all substrings of text matching pattern hash
const long long BASE = 131, MOD = 1e9 + 7;

bool rabinKarp(const string& text, const string& pat) {
    int n = text.size(), m = pat.size();
    if (m > n) return false;
    long long ph = 0, th = 0, pw = 1;
    for (int i = 0; i < m; i++) {
        ph = (ph * BASE + pat[i]) % MOD;
        th = (th * BASE + text[i]) % MOD;
        if (i) pw = pw * BASE % MOD;
    }
    if (ph == th && text.substr(0, m) == pat) return true;
    for (int i = 1; i + m <= n; i++) {
        th = (th - text[i-1] * pw % MOD + MOD) % MOD;
        th = (th * BASE + text[i + m - 1]) % MOD;
        if (th == ph && text.substr(i, m) == pat) return true;
    }
    return false;
}

典型题目

• 1044. 最长重复子串（二分长度 + 滚动哈希判断存在）
• 187. 重复的 DNA 序列（定长滑动窗口哈希）
• 28. 找出第一个匹配项（Rabin-Karp 替代 KMP）

哈希碰撞：哈希匹配后需对原字符串做精确验证（strcmp）防止碰撞误判。MOD 选大质数（如 1e9+7 或 1e9+9），BASE 选 131 或 31（适合小写字母）。

Manacher（最长回文子串）

Manacher 将奇偶长度回文统一处理：在每个字符间插入分隔符（如 #），将字符串变为奇数长度。维护回文半径数组 p[]，利用当前最右回文的中心和边界避免重复扩展，总时间 O(n)。

// Manacher's algorithm — O(n)
// Returns max palindrome length centered at each position in transformed string
vector<int> manacher(const string& s) {
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = t.size();
    vector<int> p(n, 0);
    int c = 0, r = 0; // center and right boundary of rightmost palindrome
    for (int i = 0; i < n; i++) {
        if (i < r) p[i] = min(r - i, p[2 * c - i]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i-p[i]-1] == t[i+p[i]+1])
            p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }
    }
    return p;
}

int longestPalindrome(const string& s) {
    auto p = manacher(s);
    return *max_element(p.begin(), p.end());
}

典型题目

• 5. 最长回文子串（Manacher 或 中心扩展 O(n²)）
• 647. 回文子串个数（每个 p[i] 贡献 (p[i]+1)/2 个回文）

中心扩展 vs Manacher：中心扩展法 O(n²) 但实现简单；Manacher O(n) 但较难记忆。面试中心扩展通常足够，竞赛中 Manacher 更优。