PHP实现求解最长公共子串问题的方法
发布时间：2020-12-12 22:21:43 所属栏目：PHP教程 来源：网络整理
导读：本篇章节讲解PHP实现求解最长公共子串问题的方法。供大家参考研究具体如下： 题目： 如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。 注意，并不要求子串（字符串一）的字符必须连续出现
|
本篇章节讲解PHP实现求解最长公共子串问题的方法。分享给大家供大家参考，具体如下： 题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。即，可以不连续，但顺序不能变。 请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出一个最长公共子串。 例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串， 下面的算法是根据网上的java算法由酒逍遥 翻译过来的 已经经过修正 LCS经典算法php版本= 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."rn";
echo "substring2:".$y."rn";
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 "rn";
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();
?>
运行结果： 更多关于PHP相关内容感兴趣的读者可查看本站专题：《》、《》、《》、《》、《》及《》 希望本文所述对大家PHP程序设计有所帮助。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |