php实现kmp
KMP算法简介
KMP算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt共同提出。该算法通过预处理模式串生成部分匹配表（Partial Match Table），利用已匹配信息减少不必要的比较次数，时间复杂度为O(n+m)。
PHP实现KMP算法
构建部分匹配表（PMT）
部分匹配表记录模式串前缀与后缀的最长公共长度。对于模式串$pattern，其PMT构建代码如下：
function computeLPSArray($pattern) {
$len = 0;
$lps = [0];
$i = 1;
$M = strlen($pattern);
while ($i < $M) {
if ($pattern[$i] == $pattern[$len]) {
$len++;
$lps[$i] = $len;
$i++;
} else {
if ($len != 0) {
$len = $lps[$len - 1];
} else {
$lps[$i] = 0;
$i++;
}
}
}
return $lps;
}KMP搜索实现
利用PMT进行字符串匹配，跳过已确认不匹配的部分：
function KMPSearch($pattern, $text) {
$M = strlen($pattern);
$N = strlen($text);
$lps = computeLPSArray($pattern);
$i = $j = 0;
while ($i < $N) {
if ($pattern[$j] == $text[$i]) {
$i++;
$j++;
}
if ($j == $M) {
echo "Found pattern at index " . ($i - $j) . "\n";
$j = $lps[$j - 1];
} elseif ($i < $N && $pattern[$j] != $text[$i]) {
if ($j != 0) {
$j = $lps[$j - 1];
} else {
$i++;
}
}
}
}使用示例
$text = "ABABDABACDABABCABAB";
$pattern = "ABABCABAB";
KMPSearch($pattern, $text);
// 输出：Found pattern at index 10关键点说明
- PMT构建：通过比较前缀和后缀确定最长公共长度，避免重复比较。
- 搜索优化：当字符不匹配时，根据PMT跳过已知匹配部分，减少回溯次数。
- 时间复杂度：预处理阶段O(m)，搜索阶段O(n)，优于暴力匹配的O(n*m)。
注意事项
- 模式串和文本需为单字节字符（如ASCII），多字节字符（如UTF-8）需额外处理。
- 实际应用中可封装为类，增加偏移量参数等扩展功能。
