1. 云栖社区>
  2. PHP教程>
  3. 正文

php 兑现KMP算法

作者:用户 来源:互联网 时间:2017-12-01 17:10:00

php算法kmp兑现

php 兑现KMP算法 - 摘要: 本文讲的是php 兑现KMP算法,php 实现KMP算法 <?php /** * KMP算法的PHP实现 * * @author zhaojiangwei 2011/10/22 10:28 */ class KMP{ private $next = NULL;

php 实现KMP算法 <?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; } }

以上是php 兑现KMP算法的全部内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有其他相关内容,欢迎继续使用右上角搜索按钮进行搜索php , 算法 , kmp 兑现 ,以便于您获取更多的相关知识。