KMP算法是一个比较高级的算法了，加了改进了，下面我们来在php中实现KMP算法，希望例子对各位同学会带来帮助哦。

kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息

例子

<?php
/*
字符串匹配KMP算法的PHP语言实现
*/
function KMP($str) {
    $K = array(0);
    $M = 0;
    $strLen = strlen($str);
    for($i=1; $i<$strLen; $i++) {
        if ($str[$i] == $str[$M]) {
            $K[$i] = $K[$i-1] + 1;
            $M ++;
        } else {
            $M = 0;
            $K[$i] = $K[$M];
        }
    }
    return $K;
}
// KMP查找
function KMPMatch($src, $par) {
    $K = KMP($par);
    $srcLen = strlen($src);
    $parLen = strlen($par);
    for($i=0,$j=0; $i<$srcLen; ) {
//返回完全匹配的位置
        if ($j == $parLen) return $i-$j;
//打印匹配过程
        echo $i."  ".$j. " {$src[$i]}-{$par[$j]} <BR>";
        if ($par[$j] === $src[$i]) {
//记录匹配个数
            $j++;
            $i++;
        } else {
            if ($j === 0) {
                $i++;
            }
            $j = $K[$j-1 >= 0 ? $j -1 : 0];
        }
    }
    return false;
}
// 测试下是否可用
$src = 'BBC ABCDAB ABCDABCDABDE';
$par = 'ABCDABD';
// 匹配值
echo "部分匹配值:", implode(" ", KMP($par)), "<BR>";
// 在给定的字符串中查找特定字符（串）
echo  KMPMatch($src, $par), "<BR>";
/*
部分匹配值:0 0 0 0 1 2 0
0 0 B-A
1 0 B-A
2 0 C-A
3 0  -A
4 0 A-A
5 1 B-B
6 2 C-C
7 3 D-D
8 4 A-A
9 5 B-B
10 6 -D
10 2 -C
10 0 -A
11 0 A-A
12 1 B-B
13 2 C-C
14 3 D-D
15 4 A-A
16 5 B-B
17 6 C-D
17 2 C-C
18 3 D-D
19 4 A-A
20 5 B-B
21 6 D-D
15
*/

本文地址：http://www.phprm.com/code/65015.html

转载随意，但请附上文章地址:-)