***哈哈，能破解密码的人【计算机考研】一定过！！！ *** 题目描述： ACM俱乐部的墙上写着两行密码字符串，据说能破解其中奥秘的人计算机考研一定过。 如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。 注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。 现在求ACM俱乐部两行密码字符串的最长公共子串的长度。 输入格式： 每组测试数据输入两行，每行输入一个字符串（长度<=100）。 输出: 每组测试数据输出一行，输出ACM俱乐部两行密码字符串的最长公共子串的长度。 样例输入: BDCABA ABCBDAB JXVTEWSNHACJDE LDAAJNOPPERLJBPUUNHWSYYODMGW 样例输出: 4 5 **我的分析：** 假想： 对于两个字符串x和y，有对应子串a和b,假如a和b的最长公共子 序列的长度为j, 那么c和d分别为其后面字符，ac和b的最长公共子序列的长度为 k, a和bd的最长公共子序列的长度为h; 有两种情况： 1.c和d相同，那么ac和ad的最长公共子序列的长度为j+1 2.c和d不相同，那么ac和ad的最长公共子序列的长度可能为k或 h或j 但是不论什么情况,我们只需找出这三个数的最大值 问题是j,k,h不知？？？ 例:BDCABA |—— ABCBDAB 我们从A-B统计直到最后 程序的编写： 我想到了二维数组，用me[a][b]表示两个字符串a位和b位最长 公共子序列的长度,即 me[a+1][b+1]=(me[a+1][b],me[a][b+1],me[a][b]或me[a][b]+1） 的最大值  对于任意的数组，只要边缘的数组确定了，其它的数也就确定了. 最后x和y最长公共子序列的长度就为n。 我的代码： ~~~ import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); String str1,str2; while(in.hasNextLine()){ str1=in.nextLine(); str2=in.nextLine(); int[][] me=new int[str1.length()][str2.length()];//创建一个以两个字串的长度为行列的二维数组 int oo=0; for(int j=0;j<str2.length();j++) { if(str1.charAt(0)==str2.charAt(j)&&oo==0) {me[0][j]=1;oo=1;} if(oo==1) me[0][j]=1; } oo=0; for(int j=0;j<str1.length();j++) { if(oo==0&&str1.charAt(j)==str2.charAt(0)){ me[j][0]=1;oo=1;} if(oo==1) me[j][0]=1; }//把数组的边缘的长度填充完整 int a=1,b=0; while(a<str1.length()||a<str2.length()){//填充余下的数 b=a; if(b>=str1.length()) b=str1.length()-1; if(b-1<0) break; for(int j=a;j<str2.length();j++) { if(str1.charAt(b)==str2.charAt(j)) me[b][j]=Max(me[b][j-1],me[b-1][j],me[b-1][j-1]+1); else me[b][j]=Max(me[b][j-1],me[b-1][j],me[b-1][j-1]); } b=a; if(b>=str2.length()) b=str2.length()-1; if(b-1<0) break; for(int j=a;j<str1.length();j++) { if(str1.charAt(j)==str2.charAt(b)) me[j][b]=Max(me[j][b-1],me[j-1][b],me[j-1][b-1]+1); else me[j][b]=Max(me[j][b-1],me[j-1][b],me[j-1][b-1]); } a++; } System.out.println(me[str1.length()-1][str2.length()-1]); } } public static int Max(int a,int b,int c){//方法：求三个数的最大值 int max=a; if(b>max) max=b; else if(c>max) max=c; return max; } } ~~~ //这道题实质是要用算法【动态规划】，但我自己对动态规划不很理解，只能自己分析