php中字符串匹配KMP算法实现例子

/*

字符串匹配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]}
";
 
        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)), "
";
// 在给定的字符串中查找特定字符（串）

echo  KMPMatch($src, $par), "
";
 
/*

部分匹配值: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

*/