首页 / 算法 / php兑现KMP算法
php兑现KMP算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了php兑现KMP算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1972字,纯文字阅读大概需要3分钟。
内容图文
php 实现KMP算法/**
* 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;
}
}
内容总结
以上是互联网集市为您收集整理的php兑现KMP算法全部内容,希望文章能够帮你解决php兑现KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。