如何优化算法以找到两个字符串之间的最长公共子序列（LCS）？

问题描述 投票：0回答：2

一种用于有效查找两个字符串之间的 LCS 的算法：

  1. 定义两个字符串 string1 和 string2，长度分别为 m 和 n。
  2. 创建一个二维数组 dp，尺寸为 (m+1) x (n+1)。将dp的所有元素初始化为0。
  3. 从左到右 (i) 迭代 string1 的字符，从上到下 (j) 迭代 string2 的字符。
  4. 如果 string1[i] 等于 string2[j]，则 dp[i+1][j+1] 加 1。这意味着当前字符匹配，并且此时结束的 LCS 长度比LCS 以前面的字符结尾。
  5. 如果 string1[i] 不等于 string2[j]，则取 dp[i][j+1] 和 dp[i+1][j] 之间的最大值，存入 dp[i+1][ j+1]。这意味着当前字符不匹配，因此此时结束的 LCS 长度是 string1 或 string2 中前一个字符结束的 LCS 的最大值。
  6. 迭代完所有字符后，dp[m][n]的值将是string1和string2之间的LCS长度。
  7. 要检索实际的 LCS，请从 dp[m][n] 开始并通过 dp 数组回溯。如果 string1[i-1] 等于 string2[j-1]，则将该字符添加到 LCS 并沿对角线移动到 dp[i-1][j-1]。否则，如果 dp[i][j-1] 大于 dp[i-1][j]，则向左移动；如果 dp[i-1][j] 更大，则向上移动。
  8. 重复步骤 7，直到到达 dp 数组的左上角。

按照这个算法，在编程中可以找到两个字符串之间的最长公共子序列。

Java 代码示例：

public static String repeatCharacter(char ch, int length) {
    StringBuilder sb = new StringBuilder(length);
    for (int i = 0; i < length; i++) {
        sb.append(ch);
    }
    return sb.toString();
}

Scanner myObj = new Scanner(System.in);
char ch = 'X';

System.out.println("Enter size of first string");
int m = myObj.next();
String string1 = repeatCharacter(ch, m);
System.out.println("Enter size of first string");
int m = myObj.next()
String string2 = repeatCharacter(ch, n);
String lcs = "";

System.out.println("Enter first string");
string1 = myObj.nextLine(); 
System.out.println("Enter second string");
string1 = myObj.nextLine(); 
int dp[m+1][n+1];
int i, j;

for (i = 0; i < m + 1; i++) {
     for (j = 0; j < n + 1; j++) {
          dp[i][j] = 0;
     }
}

for (i = 0; i < m; i++) {
     for (j = 0; j < n; j++) {
          if (string1[i] = string2[j])
              dp[i+1][j+1]++;
          else
              dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
     }
}

i = m, j = n;
while (i > -1 && j > -1) {
    if (string1[i-1] = string2[j-1]) {
        lcs = lcs + string1[i-1];
        i--;
        j--;
    }
    else if (dp[i][j-1] > dp[i-1][j])
        i--;
    else
        j--;
}

但是，使用嵌套的 for 循环在时间和空间上都需要 O(m n) 。

如何优化这个算法的时间复杂度和空间复杂度？

西班牙语翻译

葡萄牙语翻译

java algorithm optimization dynamic-programming lcs
2个回答
1
投票

为了优化算法的时间复杂度和空间复杂度，您可以使用一维数组而不是二维数组的动态规划来实现解决方案。这种方法将空间复杂度降低到 O(min(m, n))，同时保持 O(m*n) 相同的时间复杂度。

这是使用一维数组的算法的修改版本：

import java.util.Scanner;

public class LCS {

    public static String findLCS(String string1, String string2) {
        int m = string1.length();
        int n = string2.length();

        if (m == 0 || n == 0)
            return "";

        // Create a 1D array to store the previous row of dp values
        int[] dp = new int[n + 1];

        // Iterate over the characters of string1
        for (int i = 1; i <= m; i++) {
            // Create a variable to store the previous diagonal value
            int prevDiagonal = 0;

            // Iterate over the characters of string2
            for (int j = 1; j <= n; j++) {
                // Store the current value of dp[j] before it gets updated
                int temp = dp[j];

                if (string1.charAt(i - 1) == string2.charAt(j - 1)) {
                    dp[j] = prevDiagonal + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }

                // Update prevDiagonal for the next iteration
                prevDiagonal = temp;
            }
        }

        // Construct the LCS string by backtracking through dp array
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (string1.charAt(i - 1) == string2.charAt(j - 1)) {
                lcs.insert(0, string1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[j] > dp[j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        return lcs.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the first string:");
        String string1 = scanner.nextLine();
        System.out.println("Enter the second string:");
        String string2 = scanner.nextLine();

        String lcs = findLCS(string1, string2);
        System.out.println("Longest Common Subsequence: " + lcs);
    }
}

这种方法有效地将空间复杂度从 O(mn) 降低到 O(min(m, n))，因为它只需要单个数组而不是二维数组。此外，它还保持了之前 O(mn) 的时间复杂度。

PS： 有一种更有效的算法可以找到最长公共子序列 (LCS)，称为 Hirschberg 算法。 Hirschberg算法相对于传统的动态规划确实没有提高时间复杂度；两者的时间复杂度均为 O(m * n)。然而，Hirschberg 的优势在于它的实用效率，特别是对于长字符串，因为它通过分而治之的方法减少了计算工作量和递归深度。 Hirschberg 算法的关键见解是，它不是计算整个字符串的 LCS，而是将问题划分为更小的子问题，并且只计算这些子问题的 LCS。与传统的动态编程相比，这降低了时间复杂度，特别是在处理长字符串时。

0
投票

在这种情况下，线性搜索方法更合适、更高效：

public class LCS {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter first string:");
    String string1 = scanner.nextLine();

    System.out.println("Enter second string:");
    String string2 = scanner.nextLine();

    int[][] dp = calculateLCS(string1, string2);

    String lcs = findLCS(dp, string1, string2);

    System.out.println("Length of Longest Common Subsequence: " + dp[string1.length()][string2.length()]);
    System.out.println("Longest Common Subsequence: " + lcs);
}

private static int[][] calculateLCS(String string1, String string2) {
    int m = string1.length();
    int n = string2.length();

    int[][] dp = new int[m + 1][n + 1];

    IntStream.range(0, m + 1).forEach(i -> dp[i][0] = 0);
    IntStream.range(0, n + 1).forEach(j -> dp[0][j] = 0);

    IntStream.range(0, m).forEach(i ->
            IntStream.range(0, n).forEach(j -> {
                if (string1.charAt(i) == string2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            })
    );

    return dp;
}

private static String findLCS(int[][] dp, String string1, String string2) {
    StringBuilder lcs = new StringBuilder();
    int i = string1.length(), j = string2.length();
    while (i > 0 && j > 0) {
        if (string1.charAt(i - 1) == string2.charAt(j - 1)) {
            lcs.insert(0, string1.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs.toString();
}

}

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.