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

yipeiwu_com5年前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实现数组中出现次数超过一半的数字的统计方法

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出...

PHP解析url并得到url参数方法总结

PHP 中解析 url 并得到 url 参数 这里介绍两种对url操作的方法: 1、拿到一个完整url后,如何解析该url得到里面的参数。 /** * 解析url中参数信息,返...

PHP常用技巧汇总

本文为大家分享了多个php常用技巧,供大家参考,具体内容如下 1、PHP文件读取函式 //文件读取函式 function PHP_Read($file_name) { $fd=fo...

PHP经典设计模式之依赖注入定义与用法详解

本文实例讲述了PHP经典设计模式之依赖注入定义与用法。分享给大家供大家参考,具体如下: 依赖注入的实质就是把一个类不可能更换的部分和可更换的部分分离开来,通过注入的方式来使用,从而达到解...

PHP计算近1年的所有月份

PHP计算近1年的所有月份

话不多说,请看代码:  $z = date('Y-m'); $a = date('Y-m', strtotime('-12 months')); $begin = new...