字符串算法专题：KMP、Manacher、哈希与 C++ 实战

一、字符串算法概述

字符串是编程中最常见的数据类型之一。围绕字符串，有几类经典问题：模式匹配（在长文本中找短串出现位置）、回文判定（找最长回文子串）、子串哈希（快速比较子串是否相等）。

本文聚焦三种最常考、最实用的字符串算法：

二、暴力匹配与 KMP 原理

2.1 暴力匹配为什么慢

设文本串 T 长 n，模式串 P 长 m。暴力匹配中，每当 T[i] 与 P[j] 不匹配时，i 要回退到 i-j+1，j 从 0 重新开始。这就导致已经匹配过的字符被反复比较。

2.2 KMP 核心思想

KMP 的灵魂是：当失配发生时，利用模式串已匹配部分的"最长相等前后缀"信息，决定模式串可以跳过多少位，而文本串指针 i 从不回退。

这就需要一个 next 数组，其中 next[j] 表示：模式串第 j 位失配时，j 应该跳回到哪个下标继续比较。

2.3 next 数组构造图解

以模式串 P = "ababaca" 为例，求每个位置的最长相等前后缀长度：

2.4 KMP 逐字符匹配过程

有了 next 数组后，匹配时 i 永不回退。当 T[i] 与 P[j] 失配，j 跳到 next[j-1]（因为 j-1 之前是匹配好的）。

三、KMP 模板 + 示例：LeetCode 28 实现 strStr()

题目：给你两个字符串 haystack 和 needle，找出 needle 在 haystack 中第一次出现的位置下标，不存在返回 -1。

#include <vector>
#include <string>
using namespace std;

// 构造 next 数组：next[j] = P[0..j] 的最长相等前后缀长度
vector<int> buildNext(const string& P) {
    int m = P.size();
    vector<int> next(m, 0);
    int j = 0;  // j 指向当前已匹配的前缀长度

    for (int i = 1; i < m; ++i) {
        // 当 P[i] != P[j]，j 回退到 next[j-1]，直到 j=0 或匹配
        while (j > 0 && P[i] != P[j]) {
            j = next[j - 1];
        }
        if (P[i] == P[j]) {
            j++;
        }
        next[i] = j;  // 记录最长相等前后缀长度
    }
    return next;
}

// KMP 匹配：返回 needle 在 haystack 中第一次出现的下标
int strStr(const string& haystack, const string& needle) {
    int n = haystack.size(), m = needle.size();
    if (m == 0) return 0;

    vector<int> next = buildNext(needle);
    int j = 0;  // needle 的当前指针

    for (int i = 0; i < n; ++i) {
        // 失配时 j 回退，i 从不回退
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        // needle 全部匹配完成
        if (j == m) {
            return i - m + 1;  // 返回匹配起点下标
        }
    }
    return -1;
}

四、Manacher 原理

4.1 问题背景

回文串正读反读一样。暴力中心扩展法要分别处理奇数长度和偶数长度回文，时间 O(n²)。Manacher（马拉车）算法通过巧妙预处理，统一奇偶回文并利用回文对称性实现 O(n)。

4.2 第一步：奇偶统一处理

在每个字符中间插入一个特殊分隔符（如 #），再在首尾加哨兵（避免越界判断）：

4.3 第二步：中心扩展与回文半径递推

Manacher 维护两个关键变量：center（当前最右回文的中心）和 R（当前最右回文的右边界）。利用回文对称性，新中心 i 的初始半径可以从它关于 center 的镜像点 mirror = 2*center - i 直接继承。

五、Manacher 模板 + 示例：LeetCode 5 最长回文子串

题目：给你一个字符串 s，找到 s 中最长的回文子串。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string longestPalindrome(const string& s) {
    if (s.empty()) return "";

    // 步骤1：预处理，插入分隔符统一奇偶回文
    // 例如 "abc" → "^#a#b#c#$"（首尾加哨兵 ^$ 防越界）
    string t = "^";
    for (char c : s) {
        t += '#';
        t += c;
    }
    t += "#$";

    int n = t.size();
    vector<int> P(n, 0);  // P[i] = 以 i 为中心的回文半径（含中心本身）
    int center = 0, R = 0;  // 当前最右回文的中心与右边界

    // 步骤2：线性计算 P 数组
    for (int i = 1; i < n - 1; ++i) {
        int mirror = 2 * center - i;  // i 关于 center 的对称点

        // 情况2&3：若 i 在 R 内，利用对称性给 P[i] 一个初始值
        if (i < R) {
            P[i] = min(R - i, P[mirror]);
        }

        // 从初始半径开始，尝试向两边扩展
        while (t[i + 1 + P[i]] == t[i - 1 - P[i]]) {
            P[i]++;
        }

        // 若 i 扩展出的右边界超过了 R，更新 center 和 R
        if (i + P[i] > R) {
            center = i;
            R = i + P[i];
        }
    }

    // 步骤3：找 P 数组最大值，还原回原串位置
    int maxLen = 0, maxCenter = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            maxCenter = i;
        }
    }

    // 原串起点 = (maxCenter - maxLen) / 2
    // 推导：预处理串中位置 i，对应原串下标 i/2（向下取整）
    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

六、Rabin-Karp 滚动哈希原理

6.1 核心思想

把字符串看作一个 B 进制数（B 通常取 26, 128, 256 或更大的质数），用这个数对大质数 M 取模作为哈希值。比较两个子串是否相等时，先比较哈希值——哈希不等必不相等，哈希相等再做精确比较（处理冲突）。

6.2 滚动哈希公式

七、Rabin-Karp 示例：LeetCode 187 重复 DNA 序列

题目：DNA 序列由 'A','C','G','T' 4 种字符构成。给定 DNA 字符串 s，找出所有长度为 10 且出现超过 1 次的子串。

这个题非常适合滚动哈希：4 种字符用 2 位二进制编码（A=0, C=1, G=2, T=3），长度 10 正好 20 位，B=4, M=4¹⁰=1048576，哈希值天然不溢出且无冲突。

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

vector<string> findRepeatedDnaSequences(const string& s) {
    vector<string> ans;
    int n = s.size();
    if (n <= 10) return ans;

    // 字符 → 2位编码：A=00, C=01, G=10, T=11
    unordered_map<char, int> mp = {{'A',0}, {'C',1}, {'G',2}, {'T',3}};

    const int L = 10;          // 目标子串长度
    const int B = 4;           // 4 进制
    const int BL = 1 << (L * 2); // B^L = 4^10 = 2^20，用于哈希滚动时"去掉最高位"
                                          // 注意：实际代码中 BL = B^(L-1) 更标准，这里用位运算简化
    const int MASK = BL - 1;   // 20 位掩码，等价于 mod BL

    // 第一步：计算前 L 个字符的哈希值
    int h = 0;
    for (int i = 0; i < L; ++i) {
        h = (h << 2) | mp[s[i]];  // h = h*B + mp[s[i]]，*4 等价于左移 2 位
    }

    // 记录每个哈希值出现次数
    unordered_map<int, int> cnt;
    cnt[h] = 1;

    // 第二步：滚动哈希，O(n) 遍历
    for (int i = 1; i <= n - L; ++i) {
        // 滚动公式：
        //   1. (h << 2) ：整体升一位（*B）
        //   2. & MASK  ：去掉溢出的最高位（等价于 - s[i-1]·B^L mod BL）
        //   3. | mp[s[i+L-1]] ：加上新字符
        h = ((h << 2) & MASK) | mp[s[i + L - 1]];

        cnt[h]++;
        // 第二次出现时才加入答案，避免重复输出
        if (cnt[h] == 2) {
            ans.push_back(s.substr(i, L));
        }
    }

    return ans;
}

八、总结

复习建议

• KMP：把 buildNext 当一个"模式串自己匹配自己"的 KMP 过程来理解——i 是后缀指针，j 是前缀指针，失配 j 回 next[j-1]
• Manacher：记住三步——预处理插 #、min(R-i, P[mirror]) 给初值、(maxCenter-maxLen)/2 还原起点
• Rabin-Karp：记住滚动公式 H=(H - old·B^m)*B + new，所有运算套 mod M，负数先加 M