注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。即，可以不連續(xù)，但順序不能變。

請編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長公共子串，并打印出一個(gè)最長公共子串。

例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，

下面的算法是根據(jù)網(wǎng)上的java算法由酒逍遙 翻譯過來的

已經(jīng)經(jīng)過修正

LCS經(jīng)典算法php版本:

1. <?php 
2. class LCS{ 
3.   public static function main(){ 
4.     //設(shè)置字符串長度 
5.     $substringLength1 = 20; 
6.     $substringLength2 = 20; //具體大小可自行設(shè)置 
7.     $opt=array_fill(0,21,array_fill(0,21,null)); 
8.     // 隨機(jī)生成字符串 
9.     $x = self::GetRandomStrings($substringLength1); 
10.     $y = self::GetRandomStrings($substringLength2); 
11.     $startTime = microtime(true); 
12.     // 動(dòng)態(tài)規(guī)劃計(jì)算所有子問題 
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.     } //Vevb.com 
47.     return $str; 
48.   } 
49. } 
50. LCS::main(); 
51. ?> 

運(yùn)行結(jié)果：

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