ＰＨＰ展示ＫＭＰ拓展算法思想

每一个算法，都是基于很简单的道理，不断地增加条件，限制，让它符合心意。也就没有其他的东西了。

ＫＭＰ：

也就是我自己写的一个思路，肯定我讲不清楚，我还没有那么通透，只能记录下我现在的一个思路，而且也没必要测试。

直接上代码

<?php//基本KMP算法
//看来真的不能解释，本来我还想着解释下一下算法的改进过程发现需要图形示意，算了
//在串S中找串T
//我么为了省事,研究T的特点，每个字符在T中特点，主要是相似程度
//我拿着T去和S比对，肯定有一部分是一样的，突然不一样了，
//问题就是在这个一样的地方，可以节省步骤，“我”代指T中接下来要去匹配的串
//我在T中和相似，你都和S不一样了，我再去比较，不是费事吗，真的是废物了
//怎么标记我在T中的特点，其实就是跳转信息，我想让你略过我的位置，直接过，仅此而已。
//优化只发生在T中的小循环
//这就引入了next数组，记录省事的条状信息。在next几处上发现有点不够完美，还可以更省事
//这就引入了nextVal数组
//结束，哈哈

//就是计算出来那个最初的next,来分析T的特征
functionget_next($string=''){
$i=0;
$j=0;
$next=array();
$next[1]=0;
while($i<strlen($string)){
if($j==0||substr($string,$i,1)==substr($string,$j,1)){
++$i;
++$j;
$next[$i]=$j;
}else{
$j=$next[$j];
}
}
return$next;
}


//改进，正式的话，上面那个函数就不要看了，只是体现思路
//改进的意思就是大部分一模一样
functionget_nextVal($string=''){
$i=0;
$j=0;
$nextval=array();
$nextval[0]=0;
while($i<strlen($string)){
if($j==0||substr($string,$i,1)==substr($string,$j,1)){
++$i;
++$j;
if(substr($string,$i,1)!=substr($string,$j,1)){
$nextval[$i]=$j;
}else{
$nextval[$i]=$nextval[$j];
}
}else{
$j=$nextval[$j];
}
}
return$nextval;
}


funvtionindex_KMP($Ｔ,$Ｓ){
$i=$pos;

$j=0;
$nextVal=array();

$nextVal=get_nextVal($T);
//.....后面先不写了
while($i<strlen($S)&&$j<strlen($T))){
if($j==0||substr($string,$i,1)==substr($string,$j,1)){
++$i;
++$j;
}else{
$j=nextVal[$j];
}
}
if($j>strlen($T)){
return$i-strlen($T);
}else{
return0;
}
}

注：这是一个不复杂的思路，人家研究出来的就是很多人都可以理解的。如何运用出去那才是卖油翁的熟能生巧。

注：具体的思路推导，请参考其他大牛写的文档。

愿法界众生，皆得安宁。

本文出自 “一站式解决方案” 博客，请务必保留此出处http://10725691.blog.51cto.com/10715691/1949687

更多相关文章

随机推荐