KMP算法是一種字符串匹配算法，它能夠快速查找字符串中的一個模式串。該算法最初由D.E.Knuth J.H.Morris和V.R.Pratt發明，因此也被稱為“KMP算法”，它的優點在于時間復雜度為O(n+m)，其中n為主串長度，m為模式串長度。

使用KMP算法的一個例子是查找一個長的字符串中是否含有一個短的字符串，例如在字符串“abcdefg”中查找字符串“ef”，結果應該返回字符“e”的位置，實現代碼如下：

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

該算法的核心是計算出模式串的“部分匹配表”（也稱為“失配函數”或“next數組”），它表示未匹配的字符前后綴中最長的共同元素長度。例如，如果模式串為“ababc”，則其部分匹配表應該是{0, 0, 1, 2, 0}。其中i為前綴末尾的位置，數組元素next[i]表示最大的j（小于i）使得模式串的前綴P[0,j-1]等于后綴P[i-j,i-1]。

計算部分匹配表的代碼如下：

function getNext($pattern) {
$next[0] = -1;
$k = -1;
$j = 0;
while ($j< strlen($pattern) - 1) {
if ($k == -1 || $pattern[$j] == $pattern[$k]) {
$j++;
$k++;
$next[$j] = $k;
} else {
$k = $next[$k];
}
}
return $next;
}

在實際應用中，KMP算法常用于搜索引擎實現、正則表達式匹配、網絡爬蟲等場合。