对于两个字符串,请设计一个高效算法,求他们的最长公共子序列的长度,这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui<Ui+1,Vi<Vi+1。且A[Ui] == B[Vi]。
给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。
测试样例:
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回:6
public class LCS { public int findLCS(String A, int n, String B, int m) { int dp[][] = new int[A.length()][B.length()]; dp[0][0] = A.charAt(0)==B.charAt(0) ? 1 : 0; for (int i = 1; i < A.length(); i++) { dp[i][0] = Math.max(dp[i-1][0], A.charAt(i)==B.charAt(0) ? 1 : 0); } for (int i = 1; i < B.length(); i++) { dp[0][i] = Math.max(dp[0][i-1], A.charAt(0)==B.charAt(i) ? 1 : 0); } for (int i = 1; i < A.length(); i++) { for (int j = 1; j < B.length(); j++) { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); if (A.charAt(i) == B.charAt(j)) { dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1); } } } return dp[A.length()-1][B.length()-1]; } }
相关推荐
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
最长公共子序列问题 最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含...
由此函数,把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段,第1阶段,按照式1计算X1和Yj的最长公共子序列长度L[1][j](1),第2阶段,按照2式计算X2和Yj的最长公共子序列长度L[2][j](1),...
C++求最长公共子序列!实用 花费了好长时间!!
算法导论实验 最长公共子序列程序源码 实验报告
最长公共子序列的算法实现,采用递归方法。
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
用Python实现动态规划中最长公共子序列和最长公共子串问题!
最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
实现了求最长公共子序列的算法,内容简单易懂,代码也很短