1006 最长公共子序列Lcs

基准时间限制：1 秒 空间限制：131072 KB

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

第1行：字符串A

第2行：字符串B

(A,B的长度 <= 1000)

Output

输出最长的子序列，如果有多个，随意输出1个。

Input示例

abcicba

abdkscab

Output示例

abca

import java.util.Scanner;

import java.util.Stack;

public class Main {

    static int dp[][];

    static char a[];

    static char b[];

    static void LCS(int n,int m){

        for(int i=1;i<=n;i++){

            for(int j=1;j<=m;j++){

                if(a[i-1]==b[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]);

            }

        }

    }

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Scanner sc=new Scanner(System.in);

        while(sc.hasNext()){

            a=sc.next().toCharArray();

            b=sc.next().toCharArray();

            int len1=a.length;

            int len2=b.length;

            dp=new int[len1+1][len2+1];

            LCS(len1,len2);

            Stack<String > stack=new Stack<String>();

            int i=len1,j=len2;

            while(dp[i][j]!=0){

                if(dp[i][j]==dp[i-1][j])i--;

                else if(dp[i][j]==dp[i][j-1])j--;

                else {stack.push(a[i-1]+"");i--;j--;}        

            }

            String ans="";

            while(!stack.isEmpty()){

            ans+=stack.pop();

            }

            System.out.println(ans);

        }

        sc.close();

    }

}

1006 最长公共子序列Lcs

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏  关注

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

第1行：字符串A

第2行：字符串B

(A,B的长度 <= 1000)

Output

输出最长的子序列，如果有多个，随意输出1个。

Input示例

abcicba

abdkscab

Output示例

abca

*/

import java.util.Scanner;

import java.util.Stack;

public class Main {

static int dp[][];

static char a[];

static char b[];

static void LCS(int n,int m){

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

if(a[i-1]==b[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]);

}

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc=new Scanner(System.in);

while(sc.hasNext()){

a=sc.next().toCharArray();

b=sc.next().toCharArray();

int len1=a.length;

int len2=b.length;

dp=new int[len1+1][len2+1];

LCS(len1,len2);

Stack<String > stack=new Stack<String>();

int i=len1,j=len2;

while(dp[i][j]!=0){

if(dp[i][j]==dp[i-1][j])i--;

else if(dp[i][j]==dp[i][j-1])j--;

else {stack.push(a[i-1]+"");i--;j--;}

}

String ans="";

while(!stack.isEmpty()){

ans+=stack.pop();

}

System.out.println(ans);

}

sc.close();

}

}