/**
 * Copyright © https://github.com/microwind All rights reserved.
 * 
 * @author: jarryli@gmail.com
 * @version: 1.0
 */

/**
 * 字符串算法 - 最长公共子序列 (Longest Common Subsequence, LCS)
 * 
 * 算法原理:
 * 1. 子序列定义:在不改变相对顺序的情况下,从原序列中删除零个或多个元素后得到的序列。
 * 2. 子序列不要求连续,但必须保持原有的先后顺序。
 * 3. 使用动态规划求解:
 * - 如果 word1[i-1] == word2[j-1],则 dp[i][j] = dp[i-1][j-1] + 1
 * - 否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 * 
 * 时间复杂度:O(m * n)
 * 空间复杂度:O(m * n),可优化至 O(min(m, n))
 */
public class LongestCommonSubsequence {

 /**
 * 求解最长公共子序列
 * 
 * @param s1 第一个字符串
 * @param s2 第二个字符串
 * @return 包含长度和具体内容的数组
 */
 public static String[] findLCS(String s1, String s2) {
 int m = s1.length();
 int n = s2.length();
 
 // dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
 int[][] dp = new int[m + 1][n + 1];
 
 // 填充 DP 表
 for (int i = 1; i <= m; i++) {
 for (int j = 1; j <= n; j++) {
 if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
 // 字符匹配,继承左上角结果 + 1
 dp[i][j] = dp[i - 1][j - 1] + 1;
 } else {
 // 字符不匹配,取上方或左方的最大值
 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
 }
 }
 }
 
 // 回溯还原具体子序列内容
 StringBuilder sb = new StringBuilder();
 int i = m, j = n;
 while (i > 0 && j > 0) {
 if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
 // 相等字符属于 LCS
 sb.append(s1.charAt(i - 1));
 i--;
 j--;
 } else if (dp[i - 1][j] >= dp[i][j - 1]) {
 // 向上回退
 i--;
 } else {
 // 向左回退
 j--;
 }
 }
 
 String lcs = sb.reverse().toString();
 return new String[]{String.valueOf(dp[m][n]), lcs};
 }

 /**
 * 运行测试用例
 */
 public static void runTests() {
 String[][] testCases = {
 {"ABCBDAB", "BDCAB", "4", "BCAB,BDAB"},
 {"HELLO", "HELLO", "5", "HELLO"},
 {"ABCDEF", "ACE", "3", "ACE"},
 {"ABCD", "EFGH", "0", ""},
 {"XMJYAUZ", "MZJAWXU", "4", "MJAU,MZAU"},
 // 修正后的测试用例 10
 {"123@abc", "a3@x1", "2", "3@,1@,3a"}
 };
 
 System.out.println("LCS 测试结果:");
 for (int i = 0; i < testCases.length; i++) {
 String s1 = testCases[i][0];
 String s2 = testCases[i][1];
 String expectedLen = testCases[i][2];
 String[] possibleResults = testCases[i][3].split(",");
 
 String[] result = findLCS(s1, s2);
 String actualLen = result[0];
 String actualLCS = result[1];
 
 boolean lenMatch = actualLen.equals(expectedLen);
 boolean contentMatch = false;
 for (String p : possibleResults) {
 if (p.equals(actualLCS)) {
 contentMatch = true;
 break;
 }
 }
 
 System.out.printf("用例 %d: [%s] vs [%s] | 长度: %s (预期: %s) | 内容: %s | 状态: %s\n",
 i + 1, s1, s2, actualLen, expectedLen, actualLCS, (lenMatch ? "OK" : "FAIL"));
 }
 }

 public static void main(String[] args) {
 runTests();
 }
}