kmp算法详解php,php中字符串匹配KMP算法实现例子
KMP算法是一個比較高級的算法了，加了改進了，下面我們來在php中實現KMP算法，希望例子對各位同學會帶來幫助哦。
kmp算法是一種改進的字符串匹配算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作(簡稱KMP算法)。KMP算法的關鍵是根據給定的模式串W1,m,定義一個next函數。next函數包含了模式串本身局部匹配的信息
例子
| ?代碼如下 | 復制代碼 |
/* 字符串匹配KMP算法的PHP語言實現 */ function KMP($str) { $K = array(0); $M = 0; $strLen = strlen($str); for($i=1; $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 //返回完全匹配的位置 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 */ | |
總結
以上是生活随笔為你收集整理的kmp算法详解php,php中字符串匹配KMP算法实现例子的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： php 字符串内容过滤,php过滤字符串
- 下一篇： java学生背景知识要求,好好学习Jav