<?php
/**
* KMP算法的PHP实现
*
* @author zhaojiangwei 2011/10/22 10:28
*/
class KMP{
private $next = NULL; //模式串T的next数组
private $t = NULL; //模式串
private $str = NULL; //主串
public function KMP($str){
$this->str = str_split($str);
$this->next = array();
}
//返回主串的长度
public function getStrCount(){
return count($this->str);
}
//返回结果
public function getStrPos($substr){
$substr = str_split($substr);
$this->getNext($substr);
$strCount = $this->getStrCount();
$substrCount = count($substr);
$subIndex = 0;//子串的起始比较位置
$strIndex = 0;//主串目前的比较到的位置
while($subIndex < $substrCount && ($strCount - $strIndex) >= ($substrCount - $subIndex)){
if($subIndex == -1 || $this->str[$strIndex] == $substr[$subIndex]){
$subIndex ++;
$strIndex ++;
}else{
$subIndex = $this->next[$subIndex];
}
}
if($subIndex == $substrCount){
return $strIndex - $substrCount;
}else{
return false;
}
}
//求模式串的NEXT数组
public function getNext($t){
if(!is_array($t)){
$t = str_split($t);
}
$this->next[0] = -1;
$count = count($t);
$i = 0;
$j = -1;
while($i < $count){
if($j == -1 || $t[$i] == $t[j]){
$j ++;
$i ++;
if($t[$i] == $t[$j]){
$this->next[$i] = $this->next[$j];
}else{
$this->next[$i] = $j;
}
}else{
$j = $this->next[$j];
}
}
return $this->next;
}
}
分享到:
相关推荐
C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现...
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
JAVA实现KMP算法,使用java语言实现的kmp算法
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
KMP算法
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
kmp算法 kmp算法_基于openMP实现kmp算法
kmp算法 kmp算法_基于cuda实现kmp算法
kmp算法 kmp算法_基于Haskell实现kmp算法
kmp算法 kmp算法_基于Rust实现kmp算法
kmp算法 kmp算法_基于C语言实现KMP算法
java实现的kmp算法,参照原论文实现的,希望能有用
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
帮助了解KMP算法 KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。