PHP KMP算法——字符串匹配 KMP算法，全稱為Knuth–Morris–Pratt算法，是一種用于字符串匹配的算法。該算法的特點是具有較高的時間效率和空間效率。實現KMP算法的代碼非常簡單，是PHP程序員必會的一項技能。 一般情況下，我們匹配兩個字符串時，會使用暴力匹配算法，即將模式串（匹配的目標字符串）的每個字符與主串（被匹配字符串）逐個比較，如果匹配不上，則往后移動一位，直到找到匹配的子串或者到達主串的末尾。這種算法的時間復雜度非常高，一般達到O(n^2)。 但是如果我們使用KMP算法，匹配的時間復雜度將降到O(n)甚至更低的級別，大大提高了匹配效率。 KMP算法的實現思路是，在匹配字符串時，針對每個匹配失敗的位置，嘗試找出長度最長且已經匹配成功的前綴和后綴，然后將指針移動到該前綴的下一個位置繼續匹配。這樣可以快速的解決字符串匹配問題。 下面我們來看一下KMP算法的實現代碼：

function kmp($string, $pattern)
{
$next = array();
$i = 0;
$j = -1;
$next[0] = -1;
while ($i< strlen($pattern) - 1) {
if ($j == -1 || $pattern[$i] == $pattern[$j]) {
$i++;
$j++;
$next[$i] = $j;
} else {
$j = $next[$j];
}
}
$i = 0;
$j = 0;
while ($i< strlen($string) && $j< strlen($pattern)) {
if ($j == -1 || $string[$i] == $pattern[$j]) {
$i++;
$j++;
} else {
$j = $next[$j];
}
}
if ($j == strlen($pattern)) {
return $i - $j;
} else {
return -1;
}
}

上述代碼中的kmp函數用于實現KMP算法。首先，我們需要計算出模式串的next數組，找到匹配失敗時的最大前綴和最大后綴。然后，我們就可以開始匹配目標字符串和模式串了。如果匹配成功，則返回匹配的起始位置；如果匹配失敗，則返回-1。 接下來我們來看一下實際的例子。 例子1：匹配"hello world"和"world"。

$string = "hello world";
$pattern = "world";
$res = kmp($string, $pattern);
if ($res != -1) {
echo "匹配成功，起始位置為：" . $res;
} else {
echo "匹配失敗";
}

上述代碼中的$res變量表示匹配的結果，如果匹配成功則會返回匹配的起始位置，否則返回-1。 例子2：匹配"http://www.baidu.com"和"baidu"。

$string = "http://www.baidu.com";
$pattern = "baidu";
$res = kmp($string, $pattern);
if ($res != -1) {
echo "匹配成功，起始位置為：" . $res;
} else {
echo "匹配失敗";
}

上述代碼中，我們通過KMP算法來匹配"http://www.baidu.com"中的"baidu"，結果顯示匹配成功，并返回匹配的起始位置。 綜上所述，KMP算法是一種非常有效的字符串匹配算法，可以提高字符串匹配的效率，應用廣泛。當面對需要匹配較大字符串時，建議使用KMP算法，可以大大提高程序效率。