（1）最长公共子序列
说明：假如有一个字符串是abcde。那么他的子序列包括a，ab，bc，ad，abc，abe等等（这个不一定非要连续，只要每个字符取自该字符串并且保持前后顺序就可以）。现在给定两个字符串cnblogs，belong，他们的公共的序列包括bl，bo等等，求其最长的子序列
思路：其最长的子序列是blog。先理解一下书上的给的几个结论：
最后的总结很重要，逻辑就是根据这个来的。
代码：
1 <?php 2 $str1 = ‘cnblogs‘; 3 $str2 = ‘belong‘; 4 function findStr($str1, $str2) 5 { 6 if ($str1 == ‘‘ || $str2 == ‘‘) //i=0或j=0 7 return ‘‘; 8 9 while ($str1 != ‘‘ && $str2 != ‘‘) 10 { 11 if ($str1[strlen($str1) - 1] == $str2[strlen($str2) - 1]) { //X(i) = Y(j) 12 $res = substr($str1, -1) . $res; 13 list($str1, $str2) = [substr($str1, 0, -1), substr($str2, 0, -1)]; 14 } else { //X(i) != Y(j) 15 list($r1, $r2) = [findStr(substr($str1, 0, -1), $str2), findStr($str1, substr($str2, 0, -1))]; 16 $res = strlen($r1) > strlen($r2) ? $r1 . $res : $r2 . $res; //取max 17 break; 18 } 19 } 20 return $res; 21 } 22 echo findStr($str1, $str2);
补充：忽然发现有些情况可能有多解（上面的逻辑只会返回其中一个解），比如cnb1a2ogs和beaon12g，最长公共子序列不仅有n12g还有b12g等等。补充下面的代码（主要16行解决多个解的问题，之前只是取了一个值）。
代码：
1 <?php 2 $str1 = ‘cnb1a2ogs‘; 3 $str2 = ‘beaon12g‘; 4 function findStr($str1, $str2) 5 { 6 if ($str1 == ‘‘ || $str2 == ‘‘) //i=0或j=0 7 return []; 8 9 while ($str1 != ‘‘ && $str2 != ‘‘) 10 { 11 if ($str1[strlen($str1) - 1] == $str2[strlen($str2) - 1]) { //X(i) = Y(j) 12 $res = substr($str1, -1) . $res; 13 list($str1, $str2) = [substr($str1, 0, -1), substr($str2, 0, -1)]; 14 } else { //X(i) != Y(j) 15 list($r1, $r2) = [findStr(substr($str1, 0, -1), $str2), findStr($str1, substr($str2, 0, -1))]; 16 $tmp = strlen($r1[0]) > strlen($r2[0]) ? $r1 : (strlen($r1[0]) == strlen($r2[0]) ? array_merge($r1, $r2) : $r2); //取max 17 foreach ($tmp as $v) { 18 $ret[] = $v . $res; 19 } 20 break; 21 } 22 } 23 return isset($ret) ? array_unique($ret) : array_filter([$res]); 24 } 25 print_r(findStr($str1, $str2));
原文：https://www.cnblogs.com/wangjianheng/p/11725987.html