引言
字符串模式匹配是算法竞赛、信息检索和生物信息学中的核心问题。从简单的暴力匹配到高效的线性时间算法，字符串算法的演进体现了算法设计的精妙之处。本文将用 Java 深入实现 KMP（Knuth-Morris-Pratt）算法和 Manacher 算法，分别解决”子串搜索”和”最长回文子串”两大经典问题，讲解前缀函数与中心扩展的核心思想。
暴力匹配的局限
在介绍高效算法之前，先看暴力匹配的问题所在：
/**
* 暴力字符串匹配
* 时间复杂度：O(m * n)，其中 m 为文本长度，n 为模式串长度
*/
public int bruteForce(String text, String pattern) {
int m = text.length();
int n = pattern.length();
for (int i = 0; i <= m - n; i++) {
int j = 0;
while (j < n && text.charAt(i + j) == pattern.charAt(j)) {
j++;
}
if (j == n) {
return i; // 在位置 i 找到匹配
}
}
return -1; // 未找到匹配
}
暴力匹配的问题在于：每次匹配失败后，文本指针只回溯一位，模式串指针归零。这意味着已经比较过的字符可能被重复比较多次。KMP 算法的核心思想就是避免这种不必要的回溯。
KMP 算法：线性时间模式匹配
核心思想
KMP 算法的关键在于前缀函数（Prefix Function），也称失配函数（Failure Function）。对于模式串的每个位置 i，pi[i] 表示子串 pattern[0..i] 的最长相等真前缀与真后缀的长度。
当在位置 i 发生失配时，利用前缀函数可以直接将模式串向右移动到一个合理的位置，而无需回溯文本指针。
前缀函数的计算
/**
* 计算前缀函数（失配函数）
* pi[i] 表示 pattern[0..i] 的最长相等真前缀与真后缀的长度
* 时间复杂度：O(n)
*
* @param pattern 模式串
* @return 前缀函数数组
*/
public int[] computePrefixFunction(String pattern) {
int n = pattern.length();
int[] pi = new int[n];
// pi[0] 恒为 0，因为长度为1的字符串没有真前缀/真后缀
for (int i = 1; i < n; i++) {
int j = pi[i - 1]; // j 表示前一个位置的最长前缀后缀长度
// 如果当前字符不匹配，回退到更短的前缀
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
// 如果当前字符匹配，前缀后缀长度加1
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
pi[i] = j;
}
return pi;
}
前缀函数计算示例
以模式串 "ABABC" 为例：
| i | 子串 | 真前缀 | 真后缀 | 最长匹配 | pi[i] |
|---|---|---|---|---|---|
| 0 | A | – | – | – | 0 |
| 1 | AB | A | B | 无 | 0 |
| 2 | ABA | A, AB | A, BA | A | 1 |
| 3 | ABAB | A, AB, ABA | B, AB, BAB | AB | 2 |
| 4 | ABABC | A, AB, ABA, ABAB | C, BC, ABC, BABC | 无 | 0 |
KMP 搜索过程
/**
* KMP 字符串匹配算法
* 时间复杂度：O(m + n)，线性时间
* 空间复杂度：O(n)，用于存储前缀函数
*
* @param text 文本串
* @param pattern 模式串
* @return 模式串在文本串中首次出现的位置，未找到返回 -1
*/
public int kmpSearch(String text, String pattern) {
if (pattern.isEmpty()) return 0;
if (text.length() < pattern.length()) return -1;
int[] pi = computePrefixFunction(pattern);
int j = 0; // 模式串当前匹配位置
for (int i = 0; i < text.length(); i++) {
// 当发生失配时，利用前缀函数回退模式串指针
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
// 当前字符匹配
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
// 模式串完全匹配
if (j == pattern.length()) {
return i - pattern.length() + 1; // 返回匹配起始位置
}
}
return -1;
}
/**
* KMP 查找所有匹配位置
*/
public List<Integer> kmpSearchAll(String text, String pattern) {
List<Integer> result = new ArrayList<>();
if (pattern.isEmpty()) return result;
int[] pi = computePrefixFunction(pattern);
int j = 0;
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == pattern.length()) {
result.add(i - pattern.length() + 1);
// 继续搜索：允许重叠匹配
j = pi[j - 1];
}
}
return result;
}
KMP 算法图解
以 text = "ABABDABACDABABCABAB"，pattern = "ABABC" 为例：
文本： A B A B D A B A C D A B A B C A B A B
模式： A B A B C
↑ 在位置4失配（D != C）
利用 pi[3] = 2，模式串向右移动，保持文本指针不动：
文本： A B A B D A B A C D A B A B C A B A B
模式： A B A B C
↑ 在位置4再次失配（D != C）
利用 pi[1] = 0，模式串继续向右移动：
文本： A B A B D A B A C D A B A B C A B A B
模式： A B A B C
↑ 继续匹配...
Manacher 算法：线性时间最长回文子串
核心思想
回文串分为奇数长度（如 "aba"）和偶数长度（如 "abba"）两种。传统中心扩展法需要分别以每个字符和每对字符为中心向两边扩展，时间复杂度为 O(n²)。
Manacher 算法的核心技巧是：插入分隔符，将所有回文串统一为奇数长度。例如 "abba" 变为 "#a#b#b#a#"，此时回文中心就是某个 # 字符。
算法实现
/**
* Manacher 算法：线性时间求解最长回文子串
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
public class ManacherAlgorithm {
/**
* 预处理：插入分隔符，统一回文串长度为奇数
* 例如 "abba" -> "#a#b#b#a#"
*
* @param s 原始字符串
* @return 处理后的字符数组
*/
private char[] preprocess(String s) {
int n = s.length();
char[] t = new char[2 * n + 1];
for (int i = 0; i < n; i++) {
t[2 * i] = '#';
t[2 * i + 1] = s.charAt(i);
}
t[2 * n] = '#';
return t;
}
/**
* Manacher 算法主函数
*
* @param s 原始字符串
* @return 最长回文子串
*/
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
char[] t = preprocess(s);
int n = t.length;
int[] p = new int[n]; // p[i] 表示以 t[i] 为中心的回文半径
int center = 0; // 当前最右回文串的中心
int right = 0; // 当前最右回文串的右边界（不含）
int maxLen = 0; // 最长回文串的长度
int start = 0; // 最长回文串在原始字符串中的起始位置
for (int i = 0; i < n; i++) {
// 利用对称性初始化 p[i]
// 如果 i 在当前最右回文串内，p[i] 至少等于其关于 center 对称点的 p 值
// 但不能超过右边界
if (i < right) {
int mirror = 2 * center - i; // i 关于 center 的对称点
p[i] = Math.min(right - i, p[mirror]);
}
// 中心扩展：尝试继续扩大以 i 为中心的回文串
int leftBound = i - (p[i] + 1);
int rightBound = i + (p[i] + 1);
while (leftBound >= 0 && rightBound < n && t[leftBound] == t[rightBound]) {
p[i]++;
leftBound--;
rightBound++;
}
// 更新最右回文串信息
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 更新最长回文串信息
// 原始回文串长度 = p[i]（因为每隔一个字符是 #，有效字符数为 p[i]）
if (p[i] > maxLen) {
maxLen = p[i];
// 计算在原始字符串中的起始位置
start = (i - p[i]) / 2;
}
}
return s.substring(start, start + maxLen);
}
/**
* 获取所有回文子串的数量
*/
public int countPalindromicSubstrings(String s) {
if (s == null || s.isEmpty()) return 0;
char[] t = preprocess(s);
int n = t.length;
int[] p = new int[n];
int center = 0, right = 0;
int count = 0;
for (int i = 0; i < n; i++) {
if (i < right) {
p[i] = Math.min(right - i, p[2 * center - i]);
}
int l = i - (p[i] + 1);
int r = i + (p[i] + 1);
while (l >= 0 && r < n && t[l] == t[r]) {
p[i]++;
l--;
r++;
}
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 以 i 为中心的回文子串数量 = p[i]
// （因为半径为1对应一个字符，半径为2对应三个字符...）
count += (p[i] + 1) / 2;
}
return count;
}
}
Manacher 算法的关键理解
- 分隔符技巧：
"abba"变为"#a#b#b#a#"，中心在索引4的#处，半径为4，对应原串长度4 - 对称性利用：如果位置
i在当前最右回文串内，其关于中心center的对称点mirror = 2*center - i的回文半径已知，可以直接利用 - 边界限制：对称点提供的初始值不能超过当前最右回文串的右边界，超出部分需要中心扩展验证
Manacher 算法图解
以 s = "babad" 为例：
预处理： # b # a # b # a # d #
索引： 0 1 2 3 4 5 6 7 8 9 10
i=0: p[0]=0, center=0, right=0
i=1: 中心扩展得到 p[1]=1 ("#b#"), 更新 center=1, right=2
i=2: i<right, mirror=0, p[2]=min(0,0)=0, 扩展得 p[2]=0
i=3: i>right, 扩展得 p[3]=3 ("#b#a#b#"), 更新 center=3, right=6
i=4: i<right, mirror=2, p[4]=min(2,0)=0, 扩展得 p[4]=0
i=5: i<right, mirror=1, p[5]=min(1,1)=1, 扩展得 p[5]=1
...以此类推
最长回文：p[3]=3，原串起始位置=(3-3)/2=0，长度=3，结果为 "bab"
完整测试代码
public class StringAlgorithmDemo {
public static void main(String[] args) {
// KMP 测试
KMPAlgorithm kmp = new KMPAlgorithm();
String text = "ABABDABACDABABCABAB";
String pattern = "ABABC";
System.out.println("文本: " + text);
System.out.println("模式: " + pattern);
System.out.println("KMP首次匹配位置: " + kmp.kmpSearch(text, pattern));
System.out.println("KMP所有匹配位置: " + kmp.kmpSearchAll(text, pattern));
// 前缀函数测试
int[] pi = kmp.computePrefixFunction("ABABC");
System.out.println("前缀函数 pi: " + java.util.Arrays.toString(pi));
// Manacher 测试
ManacherAlgorithm manacher = new ManacherAlgorithm();
String[] testCases = {"babad", "cbbd", "a", "ac", "bananas", "abacdfgdcaba"};
System.out.println("\nManacher 最长回文子串测试:");
for (String test : testCases) {
String result = manacher.longestPalindrome(test);
int count = manacher.countPalindromicSubstrings(test);
System.out.println("\"" + test + "\" -> 最长回文: \"" + result + "\", 回文子串数: " + count);
}
// 性能对比：长文本匹配
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 100000; i++) {
sb.append((char)('a' + (i % 26)));
}
String longText = sb.toString();
String longPattern = longText.substring(50000, 50010);
long start = System.currentTimeMillis();
int pos = kmp.kmpSearch(longText, longPattern);
long end = System.currentTimeMillis();
System.out.println("\nKMP在10万字符中搜索: 位置=" + pos + ", 耗时=" + (end - start) + "ms");
}
}
复杂度分析
| 算法 | 问题 | 时间复杂度 | 空间复杂度 | 关键优化 |
|---|---|---|---|---|
| 暴力匹配 | 子串搜索 | O(m × n) | O(1) | 无 |
| KMP | 子串搜索 | O(m + n) | O(n) | 前缀函数避免回溯 |
| 中心扩展 | 最长回文 | O(n²) | O(1) | 无 |
| Manacher | 最长回文 | O(n) | O(n) | 对称性 + 最右回文边界 |
总结
KMP 算法和 Manacher 算法分别代表了字符串模式匹配和回文检测领域的高效解法。KMP 通过前缀函数将模式串的自身结构信息编码为失配时的跳转表，实现了文本指针永不回溯的线性时间匹配。Manacher 通过分隔符技巧统一回文长度，再利用对称性和最右回文边界信息避免重复扩展，同样达到了线性时间复杂度。
这两种算法的共同启示是：预处理阶段投入 O(n) 的时间和空间，可以换来查询阶段 O(n) 甚至 O(1) 的性能提升。这种”以空间换时间”的思想在算法设计中具有普适性，也是理解更高级字符串数据结构（如后缀数组、后缀自动机）的基础。
