最长公共子序列

动态规划

import java.util.Scanner;

public class Main {

    public static String process(String str1, String str2) {
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
            return "";
        }
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        int[][] dp = dp(char1, char2);
        int m = str1.length() - 1;
        int n = str2.length() - 1;
        char[] res = new char[dp[m][n]];
        int index = res.length - 1;

        while (index >= 0) {
            if (n > 0 && dp[m][n] == dp[m][n - 1]) {
                n--;
            } else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
                m--;
            } else {
                res[index--] = char1[m];
                m--;
                n--;
            }
        }

        return String.valueOf(res);
    }

    public static int[][] dp(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        System.out.println(process(str1, str2));
    }
}

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

int getlenght(const string &str1,const string &str2,vector<vector<int>> &dp){
    dp[0][0]=str1[0]==str2[0] ? 1:0;
    for(int i=1;i<str1.size();i++)
        dp[i][0] = dp[i-1][0]==1 ? 1 : (str1[i]==str2[0]? 1:0);
    for(int j=1;j<str2.size();j++)
        dp[0][j] = dp[0][j-1]==1 ? 1 : (str2[j]==str1[0]? 1:0);

    for(int i=1;i<str1.size();i++){
        for(int j=1;j<str2.size();j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(str1[i]==str2[j])
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    return dp[str1.size()-1][str2.size()-1];
}
int main(){
    string str1,str2;
    getline(cin,str1);
    getline(cin,str2);
    vector<vector<int>> dp(str1.size(),vector<int>(str2.size(),0));
    int lenght=getlenght(str1,str2,dp);
    string ans;
    ans.resize(lenght);
    int index = lenght-1,x=str1.size()-1,y=str2.size()-1;
    while(index>=0){
        if(y>=1&&dp[x][y]==dp[x][y-1])
            y--;
        else if(x>=1&&dp[x][y]==dp[x-1][y])
            x--;
        else{
            ans[index--]=str1[x];
            x--;
            y--;
        }
    }
    cout<<ans;
    return 0;
}

import java.util.*;

public class Main{
    public static int count = -1;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        byte[] s1 = in.nextLine().getBytes();
        byte[] s2 = in.nextLine().getBytes();
        for(int i=0;i<s1.length;i++){
            for(int j=0;j<s2.length;j++){
                StringEquals(s1,i,s2,j);
            }
        }
        System.out.println(count);
    }
    public static void StringEquals(byte[] s1, int i, byte[] s2, int j){
        int sum = 0;
        while(i<s1.length&&j<s2.length&&s1[i]==s2[j]){
            sum++;
            i++;
            j++;
        }
        if(sum!=0){
            count = Math.max(count,sum);
        }
    }
}

笑死，在题目题目理解错的基础上（以为是连续子串），想着应该是过不了测试的（准备优化），结果过了，
请问这个测试用例是怎么设计的，这都能过？

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1,s2;
    cin>>s1;
    cin>>s2;
    vector<vector<int>>dp(s1.size()+1,vector<int>(s2.size()+1));
    for(int i=0;i<s1.size()+1;i++)
    {
        for(int j=0;j<s2.size()+1;j++)
        {
            if(i==0||j==0)
                dp[i][j]=0;
            else if(s1[i-1]==s2[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[s1.size()][s2.size()]<<endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            System.out.println(maxSubSequence(str1,str2).length() > 0 ? maxSubSequence(str1,str2):-1);
        }
    }

    public static String maxSubSequence(String str1,String str2) {
        int M = str1.length();
        int N = str2.length();
        //多添加一行一列便于初始化
        int[][] dp = new int[M+1][N+1];//dp[i][j] 表示 str1[0~i-1] 与 str2[0~j-1] 的最长公共子序列的长度
        int maxLen = 0;
        String maxSubSequence = "";
        for(int i = 1;i < M+1;i++){
            for(int j = 1;j < N+1;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-1][j],dp[i][j-1]);
                }
                if(dp[i][j] > maxLen){
                    maxLen = dp[i][j];
                    maxSubSequence += str1.charAt(i-1);
                }
            }
        }
        return maxSubSequence;
    }
}

// write your code here cpp
#include<iostream>
#include<string>
using namespace std;
class Solution {
public:
	static string fun(string& s1, string& s2) {
		int size1 = s1.size(), size2 = s2.size();
        string res;
		for(int i = 0; i < size1; ++i){
            for(int j = 0; j < size2; ++j){
                if(s1[i] == s2[j]){
                    res += s1[i];
                }
            }
        }
		return res;
	}
};

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

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

int main(){
    string s1, s2, t="";
    cin>>s1>>s2;
    int n=s1.length(), m=s2.length();
    int dp[n+1][m+1];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(s1[i]==s2[j]){
                t += s1[i];
                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<<t<<endl;
    return 0;
}

 public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String str1 = scan.nextLine();
        String str2 =scan.nextLine();
        StringBuilder sb = new StringBuilder();
        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)) {
                    sb .append(str1.charAt(i-1));
                    dp[i][j] = 1 + dp[i-1][j-1];
                }else {
                    int v1 = Math.max(dp[i-1][j], dp[i][j-1]);
                    dp[i][j] = v1;
                }
            }
        }
        System.out.println(sb);
    }

这是前一半，动态规划求最长公共子序列的长度：力扣-1143-最长公共子序列

扫了一遍他们的题解，大概是逆向遍历一遍去还原字符串

我们来看看怎么根据dp数组把这个串还原

• 其实是相当于从右下角开始，如果左边/上面有一样数值大小的数字，说明这个位置的字符对公共子序列是没有贡献的，即不是最长公共子序列中的元素，就把它压缩掉
• 当左边/上面的数字都不一样（小于），说明是有贡献的，就取出这个位置的字符（从任意一个字符串中取都可以，因为是公共的），逆序放到结果数组中
• 边界条件为0时，上面两个条件判断语句会失效，直接执行最后的else

这里其实两次遍历了dp数组，也就是说，时间复杂度是O(2M*N)，空间复杂度是二维数组+res一维数组的长度

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

int main() {

    string text1, text2;
    cin >> text1 >> text2;

    int m = text1.size(), n = text2.size();
    // dp[i][0]和dp[0][j]都初始化为0
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (text2[i - 1] == text1[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    //for (vector<int> nums : dp) {
    //    for (int num : nums) cout << num << " ";
    //    cout << endl;
    //}

    // 还原字串
    if (!dp[n][m]) cout << -1;
    else {
        vector<char> res(dp[n][m]);
        int index = dp[n][m] - 1;
        while (index >= 0) {
            if (m > 0 && dp[n][m] == dp[n][m - 1]) m--;
            else if (n > 0 && dp[n][m] == dp[n - 1][m]) n--;
            else {
                res[index--] = text2[n - 1];
                n--;
                m--;
            }
        }
        for (char ch : res) cout << ch;
    }
    return 0;
}

str1 = input()
str2 = input()
n, m = len(str1), len(str2)
dp = [[0] * n for _ in range(m)]
dp[0][0] = 0 if str1[0] != str2[0] else 1
for i in range(1, m):
    dp[i][0] = 0 if str1[0] != str2[i] else 1
    dp[i][0] = max(dp[i - 1][0], dp[i][0])
for i in range(1, n):
    dp[0][i] = 0 if str1[i] != str2[0] else 1
    dp[0][i] = max(dp[0][i - 1], dp[0][i])
for i in range(1, m):
    for j in range(1, n):
        if str2[i] == str1[j]:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1)
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

i, j = m - 1, n - 1
res = []
if dp[-1][-1] == 0:
    print(-1)
    exit()
while j >= 0 and i >= 0:
    if i > 0 and dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif j > 0 and dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        res.append(str1[j])
        i -= 1
        j -= 1
print("".join(res[::-1]))

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

string LCS(string& s1, string& s2, vector<vector<int>>& dp)
{
    int len1 = s1.size();
    int len2 = s2.size();
    int len = dp[len1][len2];
    string ans = "";
    while(len)
    {
        if(len1 >= 1 && dp[len1][len2] == dp[len1 - 1][len2])
            len1--;
        else if(len2 >= 1 && dp[len1][len2] == dp[len1][len2 - 1])
            len2--;
        else
        {
            ans = s1[--len1] + ans;
            len2--;
            len--;
        }
    }
    return ans;
}

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

import java.io.*;

public class Main{
    public static void main(String[] args)throws Exception{
        try(BufferedReader bf = new BufferedReader(new InputStreamReader(System.in))){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        String result = lcse(str1, str2);
         System.out.println(result.equals("") ? -1 : result);
        }catch(IOException e){
            e.printStackTrace();
        }
    }
     public static int[][] getdp(char[] str1,char[] str2){
        int[][] dp=new int[str1.length][str2.length];
        dp[0][0]=str1[0]==str2[0]?1:0;
        for(int i=1;i<str1.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],str1[i]==str2[0]?1:0);
        }
        for(int j=1;j<str2.length;j++){
            dp[0][j]=Math.max(dp[0][j-1],str1[0]==str2[j]?1:0);
        }
        for(int i=1;i<str1.length;i++){
            for(int j=1;j<str2.length;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                if(str1[i]==str2[j]){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        return dp;
    }
    public static String lcse(String str1,String str2){
        if(str1==null||str2==null||str1.equals("")||str2.equals("")){
            return "";
        }
        char[] chs1=str1.toCharArray();
        char[] chs2=str2.toCharArray();
        int[][] dp=getdp(chs1,chs2);
        int m=chs1.length-1;
        int n=chs2.length-1;
        char[] res=new char[dp[m][n]];
        int index=res.length-1;
        while (index>=0){
            if(n>0&&dp[m][n]==dp[m][n-1]){
                n--;
            }else if(m>0&&dp[m][n]==dp[m-1][n]){
                m--;
            }else{
                res[index--]=chs1[m];
                m--;
                n--;
            }
        }
        return String.valueOf(res);
    }
   
}

#include<iostream>
using namespace std;
const int N = 5000+10;
int end_[N][N];

string lcs(string& a, string &b) {
    int n = a.size(),m = b.size();
    int len =end_[n][m];
    string res(len,'0');
     
    while(len) {
        if(n>=1 && end_[n][m] == end_[n-1][m]) --n;
        else if(m>=1 && end_[n][m] == end_[n][m-1]) --m;
        else {
            res[--len] = a[--n];
            --m;
        }
    }
    return res;
    
}


int main() {
    string a,b;
    cin>>a>>b;
    
    
    for(int i=1;i<=a.size();++i) {
        for(int j=1;j<=b.size();++j) {
           
            end_[i][j] = max(end_[i][j-1],end_[i-1][j]);
            if(a[i-1]==b[j-1]) end_[i][j] = max(end_[i][j] ,end_[i-1][j-1]+1);
             
        }
    }
    cout << lcs(a,b) <<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
        
        
        
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = bf.readLine().toCharArray();
        char[] str2 = bf.readLine().toCharArray();
        int[][] dp = new int[str1.length+1][str2.length+1];
        int[][] dr = new int[str1.length][str2.length];
        int n = str1.length;
        int m = str2.length;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                if (str1[i-1]==str2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                    dr[i-1][j-1] = 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    dr[i-1][j-1] = dp[i-1][j]>=dp[i][j-1]?2:3;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i=n-1, j=m-1;i>=0&&j>=0;){
            if (dr[i][j]==1){
                sb.append(Character.valueOf(str1[i]));
                i--;
                j--;
            }else if (dr[i][j]==2){
                i--;
            }else if (dr[i][j]==3){
                j--;
            }
        }
        sb = sb.reverse();
        System.out.print(sb);
    }
}

C++ 思路清晰的代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5007;

int f[N][N];
int n, m;
string a, b;

void getString(int i, int j, int len) { // len表示最大公共子序列的长度
    string s;
    while (i >= 1 && j >= 1) { // 倒序还原
        if (a[i - 1] == b[j - 1]) {
            s += a[i - 1];
            i--, j--;
        } else {
            if (f[i - 1][j] >= f[i][j - 1]) { // 说明是有f[i-1][j]转移过来的
                i --;
            } else j --;
        }
    }

    reverse(s.begin(), s.end());
    cout << s << endl;
}

int main() {
    cin >> a >> b;
    n = a.size(), m = b.size();
    // "f[i][j]"表示所有A[1,...,i]与B[1,...,j]的公共子序列的集合，属性：最大值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) { 
                s
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]); // 集合"f(i-1,j)"和"f(i,j-1)"有相交部分，但求最值可重复
            }
        }
    }

    int len = f[n][m]; // 最长公共子序列的长度
    if (len == 0) cout << -1 << endl;
    else getString(n, m, f[n][m]);

    return 0;
}

public class Main{
    public static void main(String[] args){
      
    }
}

import java.util.Scanner;

public class Main{
    public int longestCommenSubSequence(String s1,String s2){
        int len1 = s1.length(),len2 = s2.length();
        int[][] dp = new int[len1+1][len2+1];
        for(int i=1;i<=len1;++i){
            for(int j=1;j<=len2;++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[len1][len2];
    }
    public static void main(String[] args){
        Main c = new Main();
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int res = c.longestCommenSubSequence(s1,s2);
        System.out.println(res);
    }
}