php 兑现KMP算法-php教程-PHP中文网

php 兑现KMP算法

2016-06-13 10:49:28原创

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入门到就业线上直播课：查看学习

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。

前端(VUE)零基础到就业课程：点击学习
清晰的学习路线+老师随时辅导答疑

自己动手写 PHP MVC 框架：点击学习
快速了解MVC架构、了解框架底层运行原理

专题推荐：nbsp subIndex this next substrCount

上一篇：php基础学习- 一些废弃的用法封锁提高性能下一篇：自己动手写 PHP MVC 框架(40节精讲/巨细/新人进阶必看)

独孤九贱(3)_JavaScript视频教程

javascript是运行在浏览器上的脚本语言，连续多年，被评为全球最受欢迎的编程语言。是前端开发必备三大法器中，最具杀伤力。如果前端开发是降龙十八掌，好么javascript就是第18掌：亢龙有悔。没有它，你的前端生涯是不完整的。《php.cn独孤九贱（3）－JavaScript视频教程》课程特色：php中文网原创幽默段子系列课程，以恶搞，段子为主题风格的php视频教程！轻松的教学风格，简短的教学模式，让同学们在不知不觉中，学会了javascript知识。

独孤九贱(6)_jQuery视频教程

jQuery是一个快速、简洁的JavaScript框架。设计的宗旨是“write Less，Do More”，即倡导写更少的代码，做更多的事情。它封装JavaScript常用的功能代码，提供一种简便的JavaScript设计模式，优化HTML文档操作、事件处理、动画设计和Ajax交互。核心特性可以总结为：具有独特的链式语法和短小清晰的多功能接口；具有高效灵活的css选择器，并且可对CSS选择器进行扩展；拥有便捷的插件扩展机制和丰富的插件。兼容各种主流浏览器，如IE 6.0+、FF 1.5+、Safari 2.0+、Opera 9.0+等,是全球最流行的前端开发框架之一。PHP中文网根据最新版本,独家录制jQuery最新视频教程,回馈PHP中文网的新老用户。

jQuery与Ajax基础与实战

jQuery是最流行的JS函数库，封装了许多实用的功能,其中最引人入胜的就是Ajax。 jQuery中的Ajax操作,语法简单,操作方便，使Ajax从未如此轻松，前端人员从此不再为与服务器异步交互而发愁,本套课程,精选了最常用的几个方法，从基本的语法到每个参数，再到具体实例进行了全面的讲解。

Git教程(60分钟全程无废话版)

Git 是一个开源的分布式版本控制系统，用于敏捷高效地处理任何或小或大的项目。 Git 是 Linus Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。 Git 与常用的版本控制工具 CVS, Subversion 等不同，它采用了分布式版本库的方式，不必服务器端软件支持

php 兑现KMP算法

相关文章推荐

相关课程推荐

独孤九贱(3)_JavaScript视频教程

独孤九贱(6)_jQuery视频教程

jQuery与Ajax基础与实战

Git教程(60分钟全程无废话版)

PHP中文网