首页 > 试题广场 >

最长公共子序列

[编程题]最长公共子序列

热度指数：6426 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

输入描述:

输入包含多组数据。

每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。

输出描述:

对应每组输入，输出最长公共子序列的长度。

示例1

输入

abcfbc abfcab
programming contest
abcd mnp

输出

4
2
0

算法知识视频讲解

Java

two倩

// write your code here
import java.util.Scanner;

/**
* Created with IntelliJ IDEA.
* Description:
* User:是two倩呀！
* Data:2022-09-23
* Time:15:36
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String str1 = scanner.next();
String str2 = scanner.next();
int[][] dp = new int[str1.length() + 1][str2.length() + 1];

for (int i = 1; i <= str1.length(); i++) {
for (int j = 1; j <= str2.length(); j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}

System.out.println(dp[str1.length()][str2.length()]);

}
}
}

发表于 2022-09-23 15:51:13 回复(0)

Java

来学习的小张

import java.util.*;
public class Main{
    public static int LCS(String m,String n){
        int lenm = m.length();
        int lenn = n.length();
        int[][] dp = new int[lenm+1][lenn+1];
        for(int i = 1;i <= lenm;i++){
            for(int j = 1;j <= lenn;j++){
                if(m.charAt(i - 1) == n.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[lenm][lenn];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String m = sc.next();
            String n = sc.next();
           int res =  LCS(m,n);
            System.out.println(res);
        }
    }
}

编辑于 2022-06-02 08:25:10 回复(0)

Java

可以0613

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext())
{
String str1 = sc.next();
String str2 = sc.next();
System.out.println(maxCommonStr(str1, str2));
}
sc.close();
}

private static int maxCommonStr(String str1, String str2) {
// if (str1 == null || str2 == null) {
// return -1;
// }
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i][j - 1] > dp[i - 1][j] ? dp[i][j - 1] : dp[i - 1][j];
}
}
}
return dp[len1][len2];

}
}

发表于 2020-03-26 20:56:13 回复(0)

Java

ShuaiHao

//注意类名必须是Main，才能进行调试
//使用res矩阵，存储子问题的结果。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String[] str = in.nextLine().split(" ");
            int resLen = longestCommonSubsequence1(str[0], str[1]);
            System.out.println( resLen );
        }
    }
    
    private static int longestCommonSubsequence1(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        if(m==0||n==0) return 0;
        //存储子问题的结果。
        //行和列的索引表示：取字符串从左到中间的子串的长度
        //索引范围：[0-m]和[0-n]
        int[][] res = new int[m+1][n+1];
        //逐行添加子问题的结果。 第一行和第一列值未初始化值，系统默认为0
        //i或j表示取字符串从左到中间的子串的长度
        for(int i=0; i<=m; i++){
            for(int j=0; j<=n; j++){
                if(i==0||j==0) 
                    res[i][j] = 0;
                else if(s1.charAt(i-1)==s2.charAt(j-1))    //i而j表示的是子串长度，所以这里要减1
                    res[i][j] = res[i-1][j-1] + 1;
                else{
                    res[i][j] = Math.max(res[i-1][j], res[i][j-1]);
                }
            }
        }
        return res[m][n];
    }
}

发表于 2018-05-30 22:43:44 回复(0)