注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。即，可以不连续，但顺序不能变。

请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出一个最长公共子串。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，

下面的算法是根据网上的java算法由酒逍遥 翻译过来的

已经经过修正

LCS经典算法php版本:

1. <?php 
2. class LCS{ 
3.   public static function main(){ 
4.     //设置字符串长度 
5.     $substringLength1 = 20; 
6.     $substringLength2 = 20; //具体大小可自行设置 
7.     $opt=array_fill(0,21,array_fill(0,21,null)); 
8.     // 随机生成字符串 
9.     $x = self::GetRandomStrings($substringLength1); 
10.     $y = self::GetRandomStrings($substringLength2); 
11.     $startTime = microtime(true); 
12.     // 动态规划计算所有子问题 
13.     for ($i = $substringLength1 - 1; $i >= 0; $i--){ 
14.       for ($j = $substringLength2 - 1; $j >= 0; $j--){ 
15.         if ($x[$i] == $y[$j]) 
16.           $opt[$i][$j] = $opt[$i + 1][$j + 1] + 1; 
17.         else 
18.           $opt[$i][$j] = max($opt[$i + 1][$j], $opt[$i][$j + 1]); 
19.       } 
20.     } 
21.     echo "substring1:".$x."\r\n"; 
22.     echo "substring2:".$y."\r\n"; 
23.     echo "LCS:"; 
24.     $i = 0; 
25.     $j = 0; 
26.     while ($i < $substringLength1 && $j < $substringLength2){ 
27.       if ($x[$i] == $y[$j]){ 
28.         echo $x[$i]; 
29.         $i++; 
30.         $j++; 
31.       } else if ($opt[$i + 1][$j] >= $opt[$i][$j + 1]) 
32.         $i++; 
33.       else 
34.         $j++; 
35.     } 
36.     $endTime = microtime(true); 
37.     echo "\r\n"; 
38.     echo "Totle time is " . ($endTime - $startTime) . " s"; 
39.   } 
40.   public static function GetRandomStrings($length){ 
41.     $buffer = "abcdefghijklmnopqrstuvwxyz"; 
42.     $str=""; 
43.     for($i=0;$i<$length;$i++){ 
44.       $random=rand(0,strlen($buffer)-1); 
45.       $str.=$buffer[$random]; 
46.     } //phpfensi.com 
47.     return $str; 
48.   } 
49. } 
50. LCS::main(); 
51. ?> 

运行结果：

1. substring1:cgqtdaacneftabsxvmlb 
2. substring2:suwjwwakzzhghbsmnksg 
3. LCS:absm 
4. Totle time is 0.000648975372314 s 

Tags: PHP最长子串 PHP公共子串

分享到：