KMP算法是高效字符串匹配算法，核心是避免主串指针回退，利用最长相等前后缀信息滑动模式串，最坏时间复杂度O(n+m)，关键在于构建next数组。
什么是 KMP 算法
KMP（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，核心思想是**避免主串指针回退**。当模式串与主串某次匹配失败时，KMP 利用已匹配部分的“最长相等前后缀”信息，让模式串尽可能向右滑动，跳过不必要的比较。相比暴力匹配 O(n×m)，KMP 最坏时间复杂度为 O(n+m)。
构建 next 数组（部分匹配表）
next[i] 表示模式串 pattern[0..i] 的最长相等真前缀与真后缀的长度。它是 KMP 的关键预处理步骤。
构建逻辑：用两个指针 i（当前处理位置）、j（前缀末尾位置，也代表当前已知最长前后缀长）。初始 j = 0；遍历 i 从 1 到 len-1：
- 若 pattern[i] == pattern[j]，则 j++，next[i] = j
- 否则，回退 j = next[j−1]（直到 j==0 或 pattern[i]==pattern[j]）
- 若最终仍不等，则 next[i] = 0
PHP 实现完整 KMP 匹配函数
以下是一个清晰、可直接运行的 PHP 实现（兼容 PHP 7+）：
立即学习“PHP免费学习笔记（深入）”；
function buildNext($pattern) {
$len = strlen($pattern);
if ($len == 0) return [];
$next = array_fill(0, $len, 0);
$j = 0;
for ($i = 1; $i < $len; $i++) {
while ($j > 0 && $pattern[$i] !== $pattern[$j]) {
$j = $next[$j - 1];
}
if ($pattern[$i] === $pattern[$j]) {
$j++;
}
$next[$i] = $j;
}
return $next;
}
<p>function kmpSearch($text, $pattern) {
if (empty($pattern)) return 0;
if (empty($text)) return -1;</p><pre class='brush:php;toolbar:false;'>$next = buildNext($pattern);
$n = strlen($text);
$m = strlen($pattern);
$j = 0; // 模式串指针
for ($i = 0; $i < $n; $i++) {
while ($j > 0 && $text[$i] !== $pattern[$j]) {
$j = $next[$j - 1];
}
if ($text[$i] === $pattern[$j]) {
$j++;
}
if ($j === $m) {
return $i - $m + 1; // 返回首次匹配起始下标
}
}
return -1; // 未找到}
// 示例用法： $text = "ABABDABACDABABCABCABC"; $pattern = "ABABCABC"; var_dump(kmpSearch($text, $pattern)); // int(10)
注意事项与优化点
PHP 中字符串支持下标访问（如 $s[0]），但需注意：对 UTF-8 多字节字符，此方式会按字节而非字符切分。若需支持中文等，应先用 mb_internal_encoding('UTF-8') 并改用 mb_substr 和自定义索引逻辑，或转为数组处理。
实际项目中，除非有特殊需求（如教学、嵌入式限制、需返回所有匹配位置），一般直接使用内置函数 strpos() —— 它底层已高度优化，且对多数场景足够快。
