PHP实现求解最长公共子串问题的方法
这篇文章主要介绍了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实现求解最长公共子串问题的方法希望对你有所帮助。
-
mail.ru是什么邮箱 mail.ru邮箱登录入口 时间:2025-09-10
-
输入gpedit.msc找不到文件的原因及解决方案 时间:2025-09-10
-
nrg是什么格式文件?nrg文件用什么打开? 时间:2025-09-10
-
JavaScript中removeChild删除所有子节点方法详解(附代码) 时间:2025-09-10
-
Java运行时异常(RuntimeException)的原因及解决办法 时间:2025-09-10
-
PHP中随机数生成的方法有哪些(生成随机数的函数) 时间:2025-09-10
今日更新
-
通天排屋梗揭秘:网络热词背后的幽默文化解析
阅读:18
-
通讯兵的梗是什么梗?揭秘战场传令兵爆笑日常,看完笑到信号中断!
阅读:18
-
逆水寒手游社交能量怎么刷-社交能量获取
阅读:18
-
如鸢九月洞窟懒人版-戏学核爆与二星徐庶怎么过
阅读:18
-
最终幻想14新版本9月11日将更新-全新副本来袭
阅读:18
-
世界之外9月10日夏萧因生日更新公告完整版
阅读:18
-
闪暖×开心消消乐联动活动-9月12日更新后开启
阅读:18
-
明日之后感染者驱逐行动明日开启-珍贵奖励惊喜兑换
阅读:18
-
通讯兵梗源自军事幽默 指传递消息时总爱添油加醋的队友 网友调侃现代版传话游戏 笑点在于信息越传越离谱
阅读:18
-
原神月之一版本空月之歌呈示更新公告-完整版公告
阅读:18