本文实例讲述了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."\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();
?>
运行结果：
更多关于PHP相关内容感兴趣的读者可查看本站专题：《》、《》、《》、《》、《》及《》
希望本文所述对大家PHP程序设计有所帮助。
由 dawei
【声明】：唐山站长网内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。