问题：在长度为 ( N ) 的文本中查找长度为 ( M ) 的模式字符串（子字符串），返回首次匹配位置或所有匹配位置。
示例：文本 "INAHAYSTACKNEEDLEINA"，模式 "NEEDLE"，匹配位置 11。
特点：
( M \ll N )（模式短，文本长）。
需预处理模式以加速查找。
应用：
文本编辑器/浏览器搜索。
通信拦截（关键词检测）。
互联网大数据搜索。
二、暴力子字符串查找算法
1. 实现
思想：逐位检查文本中每个可能的 ( M ) 长子串。
代码（隐式回退）：
java
public static int search(String pat, String txt) {
int M = pat.length(), N = txt.length();
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (txt.charAt(i + j) != pat.charAt(j)) break;
if (j == M) return i; // 匹配成功
}
return N; // 未找到
}
显式回退版本：
java
public static int search(String pat, String txt) {
int M = pat.length(), N = txt.length();
for (int i = 0, j = 0; i < N && j < M; i++) {
if (txt.charAt(i) == pat.charAt(j)) j++;
else { i -= j; j = 0; }
if (j == M) return i - M;
}
return N;
}
2. 性能
最坏情况：( O(MN) )
示例：文本 "AAAAAAB"，模式 "AAAAB"，需比较 ( M(N-M+1) ) 次。
一般情况：( O(N) )
多数比较在首字符失败，平均每次 ( \sim 1 ) 次比较。
命题 M：最坏情况下需 ( \sim NM ) 次字符比较。
3. 优缺点
优点：简单，利用硬件特性优化后性能不差。
缺点：重复文本（如二进制数据）效率低。
三、Knuth-Morris-Pratt (KMP) 算法
1. 思想
核心：利用已匹配信息避免文本指针回退。
关键：匹配失败时，模式指针 ( j ) 跳转到合适位置，文本指针 ( i ) 只前进。
工具：确定有限状态自动机（DFA），记录模式指针回退距离。
2. DFA 构造
定义：dfa[c][j] 表示在状态 ( j ) 遇到字符 ( c ) 时，下一状态。
匹配：dfa[pat.charAt(j)][j] = j + 1。
不匹配：回退到与已知文本重叠最长的前缀位置。
代码：
java
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++) dfa[c][j] = dfa[c][X]; // 复制失败跳转
dfa[pat.charAt(j)][j] = j + 1; // 匹配前进
X = dfa[pat.charAt(j)][X]; // 更新重启状态
}
示例：模式 "ABABAC"，DFA 见图 5.3.9。
3. 查找实现
代码：
java
public int search(String txt) {
int N = txt.length(), M = pat.length();
for (int i = 0, j = 0; i < N && j < M; i++)
j = dfa[txt.charAt(i)][j];
return j == M ? i - M : N;
}
4. 性能
命题 N：字符访问次数 ( \leq M + N )。
DFA 构造：( O(MR) )（( R ) 为字母表大小）。
查找：( O(N) )。
空间：( O(MR) )。
5. 优缺点
优点：线性时间，无回退，适合流输入。
缺点：预处理复杂，空间需求高，对非重复模式优势不明显。
四、Boyer-Moore 算法
1. 思想
核心：从右向左匹配，利用不匹配字符跳跃。
工具：right[] 数组记录字符在模式中最右位置。
2. 实现
跳跃表构造：
java
right = new int[R];
for (int c = 0; c < R; c++) right[c] = -1;
for (int j = 0; j < M; j++) right[pat.charAt(j)] = j;
查找：
java
public int search(String txt) {
int N = txt.length(), M = pat.length();
for (int i = 0; i <= N - M; i += skip) {
skip = 0;
for (int j = M - 1; j >= 0; j--) {
if (pat.charAt(j) != txt.charAt(i + j)) {
skip = j - right[txt.charAt(i + j)];
if (skip < 1) skip = 1;
break;
}
}
if (skip == 0) return i;
}
return N;
}
3. 性能
命题 O：一般情况 ( \sim N/M ) 次比较。
最坏情况：( O(MN) )（简版，未优化）。
空间：( O(R) )。
4. 优缺点
优点：跳跃机制高效，实际性能优异。
缺点：需回退，最坏情况退化，预处理复杂。
五、Rabin-Karp 算法
1. 思想
核心：用散列值（指纹）比较子串，高效计算连续子串散列。
散列：Horner 方法，模 ( Q )（大素数）。
2. 实现
散列计算：
java
private long hash(String key, int M) {
long h = 0;
for (int j = 0; j < M; j++) h = (R * h + key.charAt(j)) % Q;
return h;
}
查找：
java
public int search(String txt) {
int N = txt.length();
long txtHash = hash(txt, M);
if (patHash == txtHash) return 0;
for (int i = M; i < N; i++) {
txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
txtHash = (txtHash * R + txt.charAt(i)) % Q;
if (patHash == txtHash) return i - M + 1;
}
return N;
}