这篇文章主要介绍了PHP实现求解最长公共子串问题的方法,简单描述了求解最长公共子串问题算法原理,并结合实例形式分析了PHP实现求解最长公共子串的具体操作技巧,需要的朋友可以参考下
本文实例讲述了PHP实现求解最长公共子串问题的方法。分享给大家供大家参考,具体如下:
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。
注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。即,可以不连续,但顺序不能变。
请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出一个最长公共子串。
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,
下面的算法是根据网上的java算法由酒逍遥 翻译过来的
已经经过修正
LCS经典算法php版本
<?php
class LCS{
public static function main(){
//设置字符串长度
$substringLength1 = 20;
$substringLength2 = 20; //具体大小可自行设置
$opt=array_fill(0,21,array_fill(0,21,null));
// 随机生成字符串
$x = self::GetRandomStrings($substringLength1);
$y = self::GetRandomStrings($substringLength2);
$startTime = microtime(true);
// 动态规划计算所有子问题
for ($i = $substringLength1 - 1; $i >= 0; $i--){
for ($j = $substringLength2 - 1; $j >= 0; $j--){
if ($x[$i] == $y[$j])
$opt[$i][$j] = $opt[$i + 1][$j + 1] + 1;
else
$opt[$i][$j] = max($opt[$i + 1][$j], $opt[$i][$j + 1]);
}
}
echo "substring1:".$x."\r\n";
echo "substring2:".$y."\r\n";
echo "LCS:";
$i = 0;
$j = 0;
while ($i < $substringLength1 && $j < $substringLength2){
if ($x[$i] == $y[$j]){
echo $x[$i];
$i++;
$j++;
} else if ($opt[$i + 1][$j] >= $opt[$i][$j + 1])
$i++;
else
$j++;
}
$endTime = microtime(true);
echo "\r\n";
echo "Totle time is " . ($endTime - $startTime) . " s";
}
public static function GetRandomStrings($length){
$buffer = "abcdefghijklmnopqrstuvwxyz";
$str="";
for($i=0;$i<$length;$i++){
$random=rand(0,strlen($buffer)-1);
$str.=$buffer[$random];
}
return $str;
}
}
LCS::main();
?>
运行结果:
substring1:cgqtdaacneftabsxvmlb
substring2:suwjwwakzzhghbsmnksg
LCS:absm
Totle time is 0.000648975372314 s
以上就是PHP实现求解最长公共子串问题的方法希望对你有所帮助。
-
J2EE是技术还是平台还是框架?什么是J2EE? 时间:2025-09-18
-
您所请求的网址(URL)无法获取的原因及解决方法 时间:2025-09-18
-
访问网站出现nginx怎么解决?welcome to nginx!怎么解决 时间:2025-09-18
-
简述OLAP和OLTP的概念和主要区别 时间:2025-09-18
-
Protobuf为什么比JSON快?两者之间的性能对比 时间:2025-09-18
-
Wifi协议802.11a/b/g/n/ac/ax是什么意思及区别 时间:2025-09-18
今日更新
-
数据库测试全流程指南:从入门到精通的实战技巧
阅读:18
-
如何高效建立数据库 从入门到精通的完整指南
阅读:18
-
天涯手游全新中式晚主题外观-晨夕绣湘君明日将登场
阅读:18
-
数据库编程入门教程:零基础快速掌握SQL与实战技巧
阅读:18
-
零基础精通数据库编程:从入门到实战的完整学习指南
阅读:18
-
无限暖暖音乐季新活动-星光绽放第二天任务完成
阅读:18
-
决战平安京S31赏金特典公布-380勾玉可全部解锁
阅读:18
-
数据加密存储的5大核心方法 如何安全保护企业敏感数据不泄露
阅读:18
-
数据结构与算法从入门到精通 零基础系统学习教程 程序员必备技能
阅读:18
-
如鸢月海夜航船精卫洱怎么打-无凌统无甄宓
阅读:18