首页 > 试题广场 >

最长公共子序列

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

热度指数：6464 时间限制：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

可以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)

我不是董皓宇。

// 参考自id：没有头的小蘑菇
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main()
{
    string s1, s2;
    while(cin>>s1>>s2)
    {
        vector<vector<int>> dp(s1.size()+1,vector<int>(s2.size()+1, 0));
        for(int i = 1; i <= s1.size(); i++)
            for(int j = 1; j<= s2.size(); j++)
            {
                if(s1[i-1] == s2[j-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
            }
        cout<<dp[s1.size()][s2.size()]<<endl;
    }
    return 0;
}

编辑于 2020-03-12 22:31:22 回复(0)

Mowar

ef findAllIndexs(string1, s):
    """
        string1: 带查找的字符串
        s: 带查找的字符
        查找当前字符在string1中的所有下标
    """
    indexlist = []
    flag = len(string1)
    while flag != -1 :
        flag = string1.rfind(s,0,flag)
        if flag > -1:
            indexlist.append(flag)

    return (s,indexlist)

def LCS_2(string1, string2):
    """
        string1: 第一个字符串
        string2: 第二个字符串
        思路:把lcs问题转化为lis问题
    """

    def conver_lis(string1,string2):
        """
            string1: 第一个字符串
            string2: 第二个字符串
            思路：求出string1 中每个字符在string2中的下标,下标从大到小排列
            其时间复杂度为O(nlogn)
        """
        lis = []
        k = set()
        for s in string1:
            if s not in k:
                ch,ind = findAllIndexs(string2, s)
                if len(ind) != 0:
                    lis.extend(ind)

        return lis

    lis = conver_lis(string1, string2)
    if len(lis) == 0:
        return 0

    q = []
    for i in lis:
        pos = bisect.bisect_left(q,i)
        if len(q) == pos:
            q.append(i)
        else:
            q[pos] = i

    return len(q)

while True:
    try:
        string1,string2 = input().split()
        res = LCS_2(string1, string2)
        print(res)
    except:
        break

..........时间复杂度为nlogn才能给过,c++只要n^2 就给过,欺负语言嘛

发表于 2018-10-15 15:15:21 回复(0)

Python

TimeMac

差劲，对Python那么不友好。根本提交不上去。查看提交过代码的同学，没一个Python的-_-

不加循环输入就说输出为空，加了循环后又说超时或算法复杂度过大？？？

try:
    while True:
        string1,string2 = input().split()
        result = [[0 for i in range(len(string2)+1)] for j in range(len(string1)+1)]
        #result[i][j]保存string1前i个子串和string2前j个子串的公共子序列
        for i in range(1,len(string1)+1):
            for j in range(1,len(string2)+1):
                result[i][j] = max(result[i-1][j],result[i][j-1])
                if string1[i-1]==string2[j-1]:
                    result[i][j] = result[i-1][j-1]+1    #等于子串都减一的公共子序列长度加一
        print(result[-1][-1])
except Exception:
    pass

编辑于 2018-09-23 20:35:56 回复(1)

classObject

//和前面问题的大佬学到的，可以试着优化一下空间效率，只保存一行，每次保存需要的值更新下一行即可
// write your code here
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            String s1=in.next();
            String s2=in.next();
            int[] dp=new int[s2.length()+1];
            for(int i=0;i<s1.length();i++){
                int pre=dp[0];
                for(int j=1;j<=s2.length();j++){
                    int temp=dp[j];
                    if(s1.charAt(i)==s2.charAt(j-1))
                        dp[j]=Math.max(dp[j],Math.max(dp[j-1],pre+1));
                    else
                        dp[j]=Math.max(dp[j],Math.max(dp[j-1],pre));
                    pre=temp;
                }
            }
            System.out.println(dp[s2.length()]);
        }
        in.close();
    }
}

发表于 2018-09-05 14:29:50 回复(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)

Python

offer到碗里

#在编译器上可以成功运行，在牛客上总是提示运行超时，不知道怎么办了
while True:
    try:
        A, B = map(str, raw_input('').split())
        n = len(A)
        m = len(B)
        matrix = [0] * m * n
        for i in range(n):
            if A[i] == B[0]:
                for j in range(i, n):
                    matrix[j] = 1
        for i in range(m):
            if B[i] == A[0]:
                for j in range(i, m):
                    matrix[j * n] = 1
        for i in range(1, m):
            for j in range(1, n):
                if B[i] == A[j]:
                    matrix[i * n + j] = max(matrix[(i - 1) * n + j - 1] + 1, matrix[(i - 1) * n + j], matrix[i * n + j - 1])
                else:
                    matrix[i * n + j] = max(matrix[(i - 1) * n + j], matrix[i * n + j - 1])
        print matrix[m * n - 1]
    except:
        break

发表于 2018-01-24 11:00:00 回复(1)

泽恩泽恩

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			String str1 = cin.next();
			String str2 = cin.next();
			lcs(str1, str2);
		}
	}
	public static void lcs(String str1, String str2) {
		int r = str1.length();
		int c = str2.length();
		if (str1.equals(str2)) {
			System.out.println(str1.length());
		} else {
			int[][] dp = new int[r][c];
			int max = 0;
			for (int i = 0; i < r; i++) {
				if (str1.charAt(i) != str2.charAt(0))
					dp[i][0] = 0;
				else {
					for (int j = i; j < r; j++)
						dp[j][0] = 1;
					break;
				}
			}
			for (int i = 0; i < c; i++) {
				if (str2.charAt(i) != str1.charAt(0))
					dp[0][i] = 0;
				else {
					for (int j = i; j < c; j++)
						dp[0][j] = 1;
					break;
				}
			}
			for (int i = 1; i < r; i++) {
				for (int j = 1; j < c; j++) {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
					if (str1.charAt(i) == str2.charAt(j))
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
					max = dp[i][j] > max ? dp[i][j] : max;
				}
			}
			System.out.println(max);
		}
	}
}

发表于 2017-09-10 16:53:34 回复(0)

后劲好大

import java.util.Scanner;

/**
 * Created by Olive on 2017/8/6.
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String strm = in.next();
            String strn = in.next();
            int cnt = longestCSS(strm, strn);
            System.out.println(cnt);
        }
    }

    public static int longestCSS(String m, String n){
        if(m == null || m.length() == 0 || n == null || n.length() == 0 )
            return 0;
        int r = m.length();
        int c = n.length();
        // dp[i][j]表示m的0~i与m的0~j子串的最长公共子串长度
        int[][] dp = new int[r][c];
        if(m.charAt(0) == n.charAt(0))
            dp[0][0] = 1;

        for(int i = 1; i < r; i++){
            dp[i][0] = m.charAt(i) == n.charAt(0) ? 1 : 0;
            dp[i][0] = Math.max(dp[i][0], dp[i - 1][0]);
        }

        for(int j = 1; j < c; j++){
            dp[0][j] = m.charAt(0) == n.charAt(j) ? 1 : 0;
            dp[0][j] = Math.max(dp[0][j], dp[0][j - 1]);
        }

        // dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        // 若m.charAt(i) == n.charAt(j):
        // dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1);
        for(int i = 1; i < r; i++){
            for(int j = 1; j < c; j++){
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if(m.charAt(i) == n.charAt(j))
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
        return dp[r-1][c-1];
    }
}

发表于 2017-08-06 16:10:37 回复(0)

ABCDEF

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int dp[1030][1030];
char a[1030];
char b[1030];
int main()
{
   while(cin>>a>>b){
    memset(dp,0,sizeof(dp));
    int lena = strlen(a);
    int lenb = strlen(b);
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            if(a[i-1]==b[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
           else
              dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[lena][lenb]<<endl;
   }
   return 0;
}

dp[i][j]表示a[i]以及之前的元素和b[i]以及之前的元素最大公共序列长度。

编辑于 2017-03-14 21:00:13 回复(0)

啥

左老师讲过，动态规划思想

建立一个dp矩阵，是两个字符串一个纵对应，一个横向对应。

dp[i][j]表示str1[0...i]和str2[0...j]的最长公共子序列的长度

求解 dp[i][j]为：

若str1[i] == str2[j]，则 dp[i][j] = max( dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1 )

若str1[i] != str2[j]，则 dp[i][j] = max( dp[i-1][j], dp[i][j-1] )

最后返回dp[M-1][N-1]，M、N为两个字符串的长度

代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    string A, B;
    while(cin >> A >> B) {
        int aLength = A.length();
        int bLength = B.length();
        vector<vector<int> > dp(aLength, vector<int>(bLength, 0));
        // 初始化边界
        dp[0][0] = (A[0] == B[0])?1:0;
        for(int i=1; i<aLength; i++) {
            dp[i][0] = (A[i] == B[0]) ? 1 : 0;
            dp[i][0] = max(dp[i-1][0], dp[i][0]);
        }
        for(int j=1; j<bLength; j++) {
            dp[0][j] = (A[0] == B[j]) ? 1 : 0;
            dp[0][j] = max(dp[0][j-1], dp[0][j]);
        }
        // 计算
        for(int i=1; i<aLength; i++) {
            for(int j=1; j<bLength; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if(A[i] == B[j]) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
                }
            }
        }
        cout << dp[aLength-1][bLength-1] << endl;
    }

    return 0;
}

发表于 2015-08-21 16:05:39 回复(0)

JacobGo！

package go.jacob.day911;

import java.util.Scanner;

public class Demo1 {
	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(LCS(str1, str2));
		}
		sc.close();
	}

	private static int LCS(String str1, String str2) {
		int len1 = str1.length(), len2 = str2.length();
		int[][] res = new int[len1 + 1][len2 + 1];

		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				int cur = 0;
				if (str1.charAt(i) == str2.charAt(j))
					cur++;

				res[i + 1][j + 1] = maxNum(res[i][j] + cur, res[i][j + 1], res[i + 1][j]);

			}
		}
		return res[len1][len2];
	}

	/*
	 * 返回三者最大值
	 */
	private static int maxNum(int i, int j, int k) {
		int max = i;
		max = j > max ? j : max;
		max = k > max ? k : max;
		return max;
	}

}

发表于 2017-09-11 11:19:16 回复(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)

牛客970492833号

import java.util.*;

public class Main {
    
    //最长公共子序列 动态规划
    //问题：字符串s1长度为m,字符串s2长度为n，求其最长公共子序列
    //状态：f(i,j)字符串s1中以i结尾的字符串和s2中以j结尾的字符串的最长公共子序列的长度
    //状态转移：f(i,j)= s1[i]==s2[j] ? f(i-1,j-1)+1 : max(f(i-1,j),f(i,(j-1))
    public static int common(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        //动态规划 二维数组初始化
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if (s1.charAt(i - 1) == s2.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[m][n];
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s1 = in.next();
            String s2 = in.next();
            System.out.println(common(s1, s2));
        }
    }
    
}

发表于 2022-05-30 17:56:39 回复(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)

打不死的黄妖精

#include<bits/stdc++.h>
#include<string>
using namespace std;

int LongestCommomSequence(string& str1,string& str2){
    if(str1.size()==0||str2.size()==0){
        return 0;
    }
    int m=str1.size();
    int n=str2.size();
    str1='0'+str1;
    str2='0'+str2;
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(str1[i]==str2[j]){
                dp[i][j]=1+dp[i-1][j-1];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        cout<<LongestCommomSequence(s1,s2)<<endl;
    } 
    return 0;
}

发表于 2020-09-15 08:51:30 回复(0)

C/C++

小周好饿

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        vector<vector<int>> dp(s1.size()+1,vector<int>(s2.size()+1,0));//dp[i][j]表示s1[0..i]和s2[0..j]的最长公子序列长度
        for(int i =1;i<=s1.size();i++){
            for(int j=1;j<=s2.size();j++){
                if(s1[i-1]==s2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
            }
        }
        cout<<dp[s1.size()][s2.size()]<<endl;
    }
    return 0;
}

编辑于 2020-03-11 17:35:28 回复(0)

上岸的小老弟

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
string A, B;
while(cin >> A >> B) {
int aLength = A.length();
int bLength = B.length();
vector<vector<int> > dp(aLength + 1, vector<int>(bLength + 1, 0));
// 初始化边界
// 计算
for(int i = 0; i < aLength; i++) {
for(int j = 0; j < bLength; j++) {
if(A[i] == B[j]) {
dp[i + 1][ j + 1] = dp[i][j] + 1;
}
else
dp[i + 1][ j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
}
}
cout << dp[aLength][bLength] << endl;
}

return 0;
}

发表于 2020-03-01 12:19:44 回复(0)

C/C++

竹寺nk

感觉全局define或者const int一个常数size，然后再创建局部二维数组int a[size][size]的方法不太完美，既然vector是个动态数组，那么就用vector咯。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int lcs(string str1, string str2) {  int len1 = str1.length();  int len2 = str2.length();  vector<vector<int>> c(len1+1, vector<int>(len2+1));  for (uint16_t i = 0; i < len1; i++) {  for (uint16_t j = 0; j < len2; j++) {  if (str1[i] == str2[j]) {  c[i+1][j+1] = c[i][j] + 1;  }  else {  c[i+1][j+1] = max(c[i+1][j], c[i][j + 1]);  }  }  }  return c[len1][len2];
}

int main()
{  int r;  string a, b;  while (cin >> a >> b)  {  if (a.empty() || b.empty())  {  break;  }  r = lcs(a, b);  cout << r << endl;  }
}

编辑于 2019-07-07 20:50:58 回复(0)

漠北孤烟

动态规划的思想。

假设字符串为A，B

建立一个数组C[i][j]记录A[0:i]和B[0:j]的最长公共子串的长度。

当A[j]==B[i]: C[i][j] = C[i-1][j-1] +1;

否则，C[i][j] = max(C[i][j-1],C[i-1][j]);

注意，给数组C多一行和一列，用作记录当A或B为空时的C的值，其实就是零，作为动态规划的初始。之后就很方便了。这里我栽了一个大坑。一开始，我的做法是直接比较B[0]和A[i]，相等C[0][i]就为1，否则就为0；同理对C[i][0]。这样处理的最大错误就是忽略的C[i][j]是记录A[0:i]和B[0:j]的最长公共子串的长度，就算是C[0][i]也是，就是不管B[0]与A[i]等不等，只要在i之前元素与B[0]相等，C[0][i]就为1。说实话这错误犯的非常傻。唉，所以，作初始的时候，给C多预留一行和一列，直接初始各自为空的，之后做下来就非常顺和简单。

完整的C++代码如下

#include<iostream>
#include<string>



using namespace std;


int main(void){     string A,B;          int res;     while(getline(cin,A,' ')&&getline(cin,B,'\n')){         int lenA = A.size()+1;         int lenB = B.size()+1;                       int C[lenB][lenA];         for(int i = 0;i<lenA;i++){             C[0][i] = 0;         }         for(int i = 1;i<lenB;i++){             C[i][0] = 0;         }              for(int i = 1;i<lenB;i++){             for(int j = 1;j<lenA;j++){                 if(B[i-1]==A[j-1]) {                     C[i][j] = C[i-1][j-1]+1;                                  }                 else C[i][j] = max(C[i-1][j],C[i][j-1]);             }         }         res = C[lenB-1][lenA-1];         cout<<res<<endl;     }          return 0;
}