PHP实现求两个字符串最长公共子串的方法示例

yipeiwu_com6年前PHP代码库

本文实例讲述了PHP实现求两个字符串最长公共子串的方法。分享给大家供大家参考,具体如下:

前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来,这里再来看另一种公共子串算法。

代码如下:

<?php
$a = 'abceee12345309878';
$b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew';
$c = array();
$lenht1 = strlen($a);
$lenth2 = strlen($b);
$startTime = microtime(true);
for ($i=0;$i<$lenht1;$i++) {
  for ($j=0;$j<$lenth2;$j++) {
    $n = ($i-1>=0 && $j-1>=0)?$c[$i-1][$j-1]:0;
    $n = ($a[$i] == $b[$j]) ? $n+1:0;
    $c[$i][$j] = $n;
  }
}
foreach ($c as $key=>$val) {
  $max = max($val);
  foreach ($val as $key1 =>$val1) {
    if ($val1 == $max && $max>0) {
      $cdStr[$max] = substr($b,$key1-$max+1,$max);
    }
  }
}
ksort($cdStr);
$endTime = microtime(true);
echo "Totle time is " . ($endTime - $startTime) . " s"."<br/>";
print_r(end($cdStr));
exit;
?>

运行结果:

Totle time is 0.0012800693512 s
abceee

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结

希望本文所述对大家PHP程序设计有所帮助。

相关文章

PHP框架Laravel的小技巧两则

用 Laravel 作为 PHP 开发框架很久了,但是有些官方文档中没有覆盖到的地方,每隔一段时间又会忘记。最近做了一点简单的整理,顺便记录下来备忘。 1. Route::control...

php根据一个给定范围和步进生成数组的方法

这里给定开始和结束值,再给定一个步进值,就可以生成一个等差数组。 function array_range($from, $to, $step=1){ $array = arra...

用 PHP5 轻松解析 XML

用 sax 方式的时候,要自己构建3个函数,而且要直接用这三的函数来返回数据,要求较强的逻辑。在处理不同结构的 xml 的时候,还要重新进行构造这三个函数,麻烦! 用 dom 方式,倒是...

php数组相加 array(“a”)+array(“b”)结果还是array(“a”)

在网上看到一道题: array("a")+array("b")的结果是___ A.array("a","b")B.array("b","a")C.array("b")D.array("a...

PHP如何实现订单的延时处理详解

PHP如何实现订单的延时处理详解

业务需求 订单是我们在日常开发中经常会遇到的一个功能,最近在做业务的时候需要实现客户下单之后订单超时未支付自动取消的功能,刚开始确认了几种方法: 客户端到时间请求取消 服务端...