java - 找到2个字符串的最长公共(public)子序列？

Question

我正在学习最长公共(public)子序列，使用这些算法:

---

公共(public)级 LCS {

static int[][] E;
static int[][] S;
static int D;
static int T;
static int L;
public static void LCS_cost(String X,String Y)
{       
    int m = X.length();
    int n = Y.length();
    E = new int[m][n];
    S = new int[m][n];
    for(int i=0;i<m;i++){
        E[i][0] = 0;
    }
    for(int j=0;j<n;j++){
        E[0][j] = 0;
    }
    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++){
            if(X.charAt(i) == Y.charAt(j)){
                E[i][j] = E[i-1][j-1]+1;
                D =  E[i-1][j-1]+1;
                S[i][j] = D;//Diagonal Direction    
            }
            else if (E[i-1][j]>=E[i][j-1]){
                    E[i][j] = E[i-1][j];
                    T = E[i-1][j];
                    S[i][j] = T;//TOP
            }
            else
                    E[i][j] = E[i][j-1];
                    L = E[i][j-1];
                    S[i][j] = L;//Left
        }
    }

}

public static void Backtrack(int[][] S,String X,String Y){
int row = X.length();
int col = Y.length();   

while (row > 0 || col > 0){
    if (S[row][col] == D){
        System.out.print(X.charAt(row));
        row--;
        col--;
    }
    else if (S[row][col] == T){
        row--;
    }
    else
        col--;
}
}
public static void main(String[] args) {
    new  LCS();
    LCS_cost("SCHOOL","SPOOL");
    Backtrack(S,"SCHOOL", "SPOOL");
    }
}

但是程序返回一个 ErrorCharAt(Unknow Source) 并且没有做任何事情。

我在努力改变

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

到

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

结果是这一行IndexOutofBoud

if (S[row][col] == D){
    ....
    }

此外，如果我将 int i 和 j 更改为 0，则下面的 E 将是索引 -1 和错误

for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(X.charAt(i) == Y.charAt(j)){
                E[i][j] = E[i-1][i-1]+1;
                ......
            }

我现在很迷茫。有人能帮帮我吗？

Answer 1

我会使用字符串而不是处理单个字符来解决这个问题:

String findLCS(String str1, String str2) {
    int longest = 0;
    String longestSubstring = "";

    for (int i=0; i < str1.length(); ++i) {
        for (int j=i+1; j <= str1.length(); ++j) {
            String substring = str1.substring(i, j);
            if (str2.contains(substring) && substring.length() > longest) {
                longest = substring.length();
                longestSubstring = substring;
            }
        }
    }

    return longestSubstring;
}

如您所见，使用 String.contains() 比看起来更强大。