实现最长公共子序列的算法,java两个字符串的最长公共子序列
如何解决写爬虫IP受阻的问题？立即使用。
实验目的：
输入两个同类型的序列，通过动态规划计算它们的最长公共子序列及其序列的长度。
(推荐教程：java视频教程)
想法：
1.首先，使用一个二维数组存储最长公共子序列的长度，并记录每个值的状态。
2.根据记录值的状态，递归回溯最长公共子序列。
3.递归方程：
代码实现：
封装最长公共子序列；
导入Java . util . scanner；
/**
* @作者德拉科
* @查看最长公共子序列()
* @版本
* @日期-时间2020-04-27-下午4:23:36
*/
公共类LCS {
公共静态void main(String[] args) {
//测试字符串：ABCBDAB BDCABA
Scanner scanner=新扫描仪(system . in)；
System.out.println(注意：第一个字符串比第二个字符串长)；
System.out.print(请输入第一个字符串：)；
string string 1=scanner . next()；
System.out.print(请输入第二个字符串：)；
string string 2=scanner . next()；
String str1=string1
String str2=string2
//String str 1= ABCBDAB ；
//String str 2= BD caba ；
int[][]c=getSubstringMatrix(str 1，str 2)；
String[][] b=getTrace(str1，str 2)；
system . out . println( length matrix:)；
展示(c)；
system . out . println()；
System.out.println(方向矩阵：)；
showForString(b)；
System.out.println(最长公共子序列的长度： C[str 1 . Length()][str 2 . Length()])；
string sMax=str 1 . length()str 2 . length()？str 1:str 2；//选择最长的字符串，因为要取出最大的子串。
string sMin=str 1 . length()str 2 . length()？str 1:str 2；//选择最小的字符串
System.out.print(最长公共子串：)；
print(b，sMax，sMax.length()，smin . length())；
}
/**
* @参见找出子序列矩阵，其中最后一行和最后一列是最长子序列的长度。
* @param x首个字符串
* @param y第二字符串
* @返回长度矩阵
*/
public static int[][]getSubstringMatrix(String x，String y) {
int xLen=x . length()1；//加1，因为第一次初始化是0。
int yLen=y . length()1；
int rLen=xLen yLen？xLen:yLen；//大型字符串作为行放置
int cLen=xLen yLen？xLen:yLen；//小字符串放在列中
int[][]c=new int[rLen][cLen]；//矩阵C保存状态
for(int I=1；i rLeni ) {
for(int j=1；j克伦；j ) {
if(x . charat(I-1)==y . charat(j-1)){
//相等，由对角线1表示
c[I][j]=c[I-1][j-1]1；
} else if (c[i - 1][j]=c[i][j - 1]) {
//不相等，选择较大的那个
c[I][j]=c[I-1][j]；
}否则{
c[I][j]=c[I][j-1]；
}
}
}
返回c；//长度矩阵
}
/**
* @see记录每个值的状态，方便回溯和递归。
* @param x首个字符串
* @param y第二字符串
* @返回方向矩阵
*/
public static String[][]getTrace(String x，String y) {
int xLen=x . length()1；
int yLen=y . length()1；
//为矩阵C和b设置行和列。
int rLen=xLen yLen？xLen:yLen；//大型字符串作为行放置
int cLen=xLen yLen？xLen:yLen；//小字符串放在列中
int[][]c=new int[rLen][cLen]；
String[][] b=新字符串[rLen][cLen]；
for(int I=1；i rLeni ) {
for(int j=1；j克伦；j ) {
if(x . charat(I-1)==y . charat(J-1)){//等于
c[I][j]=c[I-1][j-1]1；
b[I][j]= \ \ \ \ ；//指向左上角
} else if(C[I-1][J]=C[I][J-1]){//不等于
//当上述值较大时
c[I][j]=c[I-1][j]；
b[I][j]= ；//指向顶部
}否则{
//当下列值很大时
c[I][j]=c[I][j-1]；
b[I][j]= —— ；//指向左边
}
}
}
返回b；//方向矩阵
}
/**
* @see递归实现回溯，然后打印出最长的公共子序列。
* @param b方向矩阵
* @param的长字符串
* @param i较长字符串的长度
* @param j较短字符串的长度
*/
public static void print(String[][]b，String s，int i，int j) {
//递归终止的条件
if (i==0 j==0) {
返回；
}
//判断递归的条件。
if (b[i][j]。等于( \ \ \ \ ){
//遇到斜杠时递归到左上角
打印(b，s，i - 1，j-1)；
系统。出去。print(s . charat(I-1) )；
} else if (b[i][j].等于( ){
//遇到竖线，递归到上边
print(b，s，i - 1，j)；
} else if (b[i][j].等于( —— ){
//遇到横线，递归到左边
print(b，s，I，j-1)；
}
}
/**
* @见打印二维数组
* @param b一个二维数组
*/
public static void show(int[][]b){
for(int w=0；w。长度；w ) {
for(int p=0；p b[w].长度；p ) {
系统。出去。print(b[w][p] \ \ t )；
if (p==b[w].长度- 1) {
系统。出去。println()；
}
}
}
}
/**
* @见打印字符串的二维数组
* @param b一个字符串的二位数组
*/
public static void showForString(String[][]b){
for(int w=1；w。长度；w ) {
系统。出去。打印( \ \ t )；
for(int p=1；p b[w].长度；p ) {
系统。出去。print(b[w][p] \ \ t )；
if (p==b[w].长度- 1) {
系统。出去。println()；
}
}
}
}
}运行结果：
相关推荐：java入门以上就是算法学习——java实现最长公共子序列的详细内容，更多请关注我们其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。