JAVA代码—算法基础：求两个字符串的最长公共子序列问题

求两个字符串的最长公共子序列问题

最长公共子序列问题： 给定两个字符串A、B，求A与B的最长公共子序列（子序列不要求是连续的）
举例：
字符串A： abcicba
字符串B：abdkscab
其中:ab、abc、abca都是公共子序列，但是abca是最长公共子序列

从文件读取输入：
1A2C3D4B56
B1D23CA45B6A

输出：
123456
或者 12C4B6都正确

package com.bean.algorithmexec;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LCS {

/*
 * 最长公共子序列问题 给定两个字符串A、B，求A与B的最长公共子序列（子序列不要求是连续的） 
 * 举例： 
 * 字符串A： abcicba 
 * 字符串B：abdkscab
 * 其中:ab、abc、abca都是公共子序列，但是abca是最长公共子序列
 * 
 * 从文件读取输入：
 * 1A2C3D4B56
 * B1D23CA45B6A
 * 
 * 输出：
 * 123456 
 * 
 * 或者 12C4B6都正确
 * 
 * （这里的算法其实存在一个缺陷）
 */

public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub

        System.setIn(new FileInputStream("G:\\lcs.txt"));
        Scanner sc = new Scanner(System.in);

        String aStr = sc.nextLine(); //读取A字符串
        String bStr = sc.nextLine(); //读取B字符串
int aLen = aStr.length();
int bLen = bStr.length();
//构造DP矩阵
int[][] dp = new int[aLen + 1][bLen + 1];
for (int i = 1; i < aLen + 1; i++)
for (int j = 1; j < bLen + 1; j++)
if (dp[i - 1][j] == dp[i][j - 1] && aStr.charAt(i - 1) == bStr.charAt(j - 1)
                        && dp[i - 1][j] == dp[i - 1][j - 1])
                    dp[i][j] = dp[i - 1][j] + 1;
else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
int max = dp[aLen][bLen];
        StringBuilder sb = new StringBuilder();
while (max > 0) {
if (dp[aLen - 1][bLen] == dp[aLen][bLen - 1] && dp[aLen - 1][bLen] + 1 == dp[aLen][bLen]) {
                sb.append(aStr.charAt(aLen - 1));
                max--;
                aLen--;
                bLen--;
            } else {
if (dp[aLen][bLen - 1] == dp[aLen][bLen])
                    bLen--;
else
                    aLen--;
            }
        }

        System.out.println(sb.reverse().toString());
    }

}

（完）