PHP实现KMP算法
2021/8/22 9:36:17
本文主要是介绍PHP实现KMP算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
<?php//构建部分匹配表 function part_match($goal,$match=null) { static $match; $length = strlen($goal); if($length < 2){ return; } for($i=0;$i<$length-1;$i++){ $left[] = substr($goal,0,$i+1); $right[] = substr($goal,1+$i,$length-$i); } foreach(array_intersect($left,$right) as $v){ $len = strlen($v); if($len > 1){ $match[$v[$len-1]] = $len; continue; } $match[$v] = $len; } part_match(rtrim($goal,$goal[$length-1])); return $match; }
//执行kmp算法 function kmp($str,$goal) { $map = part_match($goal); if(is_null($map) || empty($map)){ return null; } $glen = strlen($goal); $result = []; @[$a,$b] = [0,0]; while($b < $glen){ if($str[$a] == $goal[$b]){ $result[$b] = $str[$a]; $a++; $b++; continue; } if($b==0){ $a++; continue; } //如果出现不匹配的情况,则a减一查找最后一次匹配顺序正确的数值 //将$goal当前的key值减去减去不需要在比较的部分得出$b要往回挪动的数值 $b = $b - ($b - $map[$str[$a-1]]); } return implode('',$result); }
$str = "BBC ABCDAB ABCDABCDABDEBDQQQDQQQQDEFDQQQQQ"; $goal = "DQQQQDEFD"; $res = kmp($str,$goal); var_dump($res);
这篇关于PHP实现KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28怎么把PHP程序打包?-icode9专业技术文章分享
- 2024-09-28怎么用Phar打包PHP程序?-icode9专业技术文章分享
- 2024-09-13手动在github上下载的mfpt包,怎么放到thinkphp5.0框架并正常使用-icode9专业技术文章分享
- 2024-09-05python的<class 'bytearray'>相当于php的哪个数据类型-icode9专业技术文章分享
- 2024-09-05php 导出银行卡号避免科学技术法的方法-icode9专业技术文章分享
- 2024-08-30什么样的php代码质量差被称为垃圾代码-icode9专业技术文章分享
- 2024-08-30用 PHP 调用拼多多的接口以获取订单状态消息的步骤方法和代码示例-icode9专业技术文章分享
- 2024-08-27phpunit单元测试框架的入门和使用方法介绍-icode9专业技术文章分享
- 2024-08-24PHP 中date("w") 周一是多少-icode9专业技术文章分享
- 2024-08-14thinkphp8.0获取域名或主机名方法-icode9专业技术文章分享