最长锚定公共序列

Question

字符串 s1, s2 的最长公共子序列是最长的字符串 s，使得 s 是 s1 和 s2 的子序列，即我们可以通过从 si 中的某个点开始，通读（也许跳过一些字母）来得到 s，然后在某个时刻停止。

假设现在我们的字母表包含一个特殊的“锚”字符 * 比普通字母绑定“更牢固”：具体来说，当读取每个 si 来查找 s 时，我们不允许跳过任何 *s（尽管在我们读取的 si 部分之外可能有 *s）。例如，假设 s1 = A * BCD* 且 s2 = B * CAD。我们不会 被允许采用子序列 BC（因为这需要跳过 s2 中的 *），但我们将被允许采用子序列 *CD，它是最长的锚定公共子序列，长度为 3。

任务： 实现 Anchored.java 以确定最长锚定公共子序列 (LACS)，其中 * 字符充当不可跳过的锚点。输入由两个字符串组成，每个字符串最多 2,000 个字符长，包含字母 A-Z 和 .

当前状态：我已经编写这个动态编程解决方案两天了，重点是处理涉及锚字符的所有可能的边缘情况。尽管我付出了努力，但我提交的代码在 Codegrade 上的许多隐藏输出案例都失败了。

挑战：该算法似乎在标准测试用例上表现良好，但在隐藏测试用例上表现不佳。我怀疑我所遗漏的 * 处理方式可能存在微妙之处，或者其他任何东西。

请求：任何人都可以帮我找出可能出了什么问题吗？任何见解，特别是在处理涉及 * 的边缘情况方面，将不胜感激。这是我的代码的最新版本：

import java.util.Scanner;
import java.io.File;
import java.io.IOException;

public class Anchored {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        String filename = scanner.nextLine();
        File infile = new File(filename);
        Scanner input = new Scanner(infile);
        String s1 = input.nextLine();
        String s2 = input.nextLine();
        input.close();
        scanner.close();

        int m = s1.length();
        int n = s2.length();
        int[][] L = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char c1 = s1.charAt(i - 1);
                char c2 = s2.charAt(j - 1);

                if (c1 == c2) {
                    L[i][j] = L[i - 1][j - 1] + 1;
                } else {
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
                }

                if (c1 == '*' || c2 == '*') {
                    if (c1 == '*' && c2 == '*') {
                        L[i][j] = L[i - 1][j - 1] + 1;
                    } else if (c1 == '*') {
                        L[i][j] = L[i - 1][j];
                    } else if (c2 == '*') {
                        L[i][j] = L[i][j - 1];
                    }
                }
            }
        }

        System.out.println(L[m][n]);
    }
}

我实现了一个动态编程解决方案来计算两个字符串之间的最长锚定公共子序列（LACS），其中 * 字符充当锚点，必须包含在子序列中而不能跳过。我使用了一个二维数组，其中每个单元格 L[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符之间的最长子序列的长度。我修改了标准 LCS 算法来处理其中一个字符为 * 的情况，确保在发生不匹配时包含 * 的序列不会被错误扩展。

Answer 1

兄弟，我们和DA在同一条船上😭