一、问题定义
字符串匹配（Pattern Matching）：在文本串 text（长度 n）中查找模式串 pattern（长度 m）出现的位置。
| 算法 | 时间复杂度 | 核心思想 |
|---|---|---|
| 暴力匹配 | O(nm) | 逐位对齐比较 |
| KMP | O(n + m) | 利用已匹配信息避免回退 |
| Rabin-Karp | O(n + m) 平均 | 哈希 + 滑动窗口 |
| Boyer-Moore | O(n/m) 最好 | 坏字符 + 好后缀 |
面试中 KMP 是绝对重点，Rabin-Karp 了解即可。
二、暴力匹配
public int strStr(String text, String pattern) {
int n = text.length(), m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
j++;
}
if (j == m) return i;
}
return -1;
}