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

KMP算法是一个比较高级的算法了,加了改进了,下面我们来在php中实现KMP算法,希望例子对各位同学会带来帮助,kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法),KMP算法的关键是根据给定的模式串W1,m,定义一个next函数,next函数包含了模式串本身局部匹配的信息.

例子,代码如下:

1. <?php 
2. /* 
3. 字符串匹配KMP算法的PHP语言实现 
4. */ 
5. function KMP($str) { 
6.     $K = array(0); 
7.     $M = 0; 
8.     $strLen = strlen($str); 
9.     for($i=1; $i<$strLen; $i++) { 
10.         if ($str[$i] == $str[$M]) { 
11.             $K[$i] = $K[$i-1] + 1; 
12.             $M ++; 
13.         } else { 
14.             $M = 0; 
15.             $K[$i] = $K[$M]; 
16.         } 
17.     }  //开源软件:Vevb.com 
18.     return $K; 
19. } 
20.  
21. // KMP查找 
22. function KMPMatch($src, $par) { 
23.     $K = KMP($par); 
24.  
25.     $srcLen = strlen($src); 
26.     $parLen = strlen($par); 
27.  
28.     for($i=0,$j=0; $i<$srcLen; ) { 
29.  
30.          
31. //返回完全匹配的位置 
32.         if ($j == $parLen) return $i-$j; 
33.  
34.          
35. //打印匹配过程 
36.         echo $i."  ".$j. " {$src[$i]}-{$par[$j]} <BR>"; 
37.  
38.         if ($par[$j] === $src[$i]) { 
39.              
40. //记录匹配个数 
41.             $j++; 
42.             $i++; 
43.         } else { 
44.             if ($j === 0) { 
45.                 $i++; 
46.             } 
47.             $j = $K[$j-1 >= 0 ? $j -1 : 0]; 
48.         } 
49.     } 
50.     return false; 
51. } 
52.  
53. // 测试下是否可用 
54. $src = 'BBC ABCDAB ABCDABCDABDE'; 
55. $par = 'ABCDABD'; 
56.  
57. // 匹配值 
58. echo "部分匹配值:", implode(" ", KMP($par)), "<BR>"; 
59. // 在给定的字符串中查找特定字符（串） 
60. echo  KMPMatch($src, $par), "<BR>"; 
61.  
62. /* 
63. 部分匹配值:0 0 0 0 1 2 0 
64. 0 0 B-A 
65. 1 0 B-A 
66. 2 0 C-A 
67. 3 0  -A 
68. 4 0 A-A 
69. 5 1 B-B 
70. 6 2 C-C 
71. 7 3 D-D 
72. 8 4 A-A 
73. 9 5 B-B 
74. 10 6 -D 
75. 10 2 -C 
76. 10 0 -A 
77. 11 0 A-A 
78. 12 1 B-B 
79. 13 2 C-C 
80. 14 3 D-D 
81. 15 4 A-A 
82. 16 5 B-B 
83. 17 6 C-D 
84. 17 2 C-C 
85. 18 3 D-D 
86. 19 4 A-A 
87. 20 5 B-B 
88. 21 6 D-D 
89. 15 
90. */ 
91. ?>