本文实例讲述了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
相信看了本文案例你已经掌握了方法，更多精彩请关注其它相关文章！
推荐阅读：
如何用swoole与websocket开发一个聊天室
php有哪些生成随机数的方法
以上就是php怎么求解最长公共子串的详细内容。