php实现kmp
PHP实现KMP算法
KMP算法是一种高效的字符串匹配算法，通过预处理模式字符串（pattern）生成部分匹配表（Partial Match Table），避免不必要的回溯，提升匹配效率。以下是PHP实现KMP算法的详细步骤：
生成部分匹配表（PMT）
部分匹配表记录了模式字符串中每个位置的最长公共前后缀长度。以下是生成PMT的PHP函数：
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;
$result = [];
while ($i < $n) {
if ($pattern[$j] == $text[$i]) {
$i++;
$j++;
}
if ($j == $m) {
array_push($result, $i - $j);
$j = $lps[$j - 1];
} elseif ($i < $n && $pattern[$j] != $text[$i]) {
if ($j != 0) {
$j = $lps[$j - 1];
} else {
$i++;
}
}
}
return $result;
}使用示例
调用KMP算法进行字符串匹配：
$text = "ABABDABACDABABCABAB";
$pattern = "ABABCABAB";
$matches = KMPSearch($pattern, $text);
if (!empty($matches)) {
echo "Pattern found at positions: " . implode(", ", $matches);
} else {
echo "Pattern not found in the text.";
}算法复杂度分析
- 时间复杂度：O(n + m)，其中n是文本长度，m是模式长度。
- 空间复杂度：O(m)，用于存储部分匹配表。
优化建议
- 对于多次重复使用的模式字符串，可缓存部分匹配表避免重复计算。
- 处理大规模文本时，考虑分批读取文本以减少内存占用。
