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

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 = &#39;BBC ABCDAB ABCDABCDABDE&#39;; 
	$par = &#39;ABCDABD&#39;; 
	 
	// 匹配值 
	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 
	*/ 
	

文章链接：

随便收藏，请保留本文地址！