动态规划有一个经典问题是最长公共子序列，但是这里的子序列不要求连续，如果要求序列是连续的，我们叫公共子串，那应该如何得到这个串呢？
最简单的方法就是依次比较，以某个串为母串，然后生成另一个串的所有长度的子串，依次去母串中比较查找，这里我们用递归查找最长公共子串。
import java.util.Scanner; public class lookup { public static int lcs(char[] x,char[] y,int i,int j) { if(i==0||j==0) return 0; else if(x[i]==y[j]) { return lcs(x,y,i-1,j-1)+1; } else return Math.max(lcs(x,y,i-1,j), lcs(x,y,i,j-1)); } public static void main(String[] args) { String x="ABCBDAB"; String y="BDCABA"; // Scanner in=new Scanner(System.in); // System.out.println("请输入父集合"); // x=in.nextLine(); // System.out.println("请输入子集合"); // y=in.nextLine(); char [] c1=new char[x.length()+1]; char [] c2=new char[y.length()+1]; char[] t1=x.toCharArray(); char [] t2=y.toCharArray(); c1[0]=(char)0; c2[0]=(char)0; for(int i=0;i<t1.length;i++) { c1[i+1]=t1[i]; } for(int i=0;i<t2.length;i++) { c2[i+1]=t2[i]; } System.out.println(lcs(c1,c2, c1.length-1, c2.length-1)); } }这里我为了方便调试，我直接将两个字符串赋值，如果想要其他的字符串直接将注释符去掉即可。
