最长公共子序列

最长公共子序列

Description

 

给定两个字符串，返回两个字符串的最长公共子序列（不是最长公共子字符串），可能是多个。

Input

 

输入第一行为用例个数， 每个测试用例输入为两行，一行一个字符串

Output

 

如果没有公共子序列，不输出，如果有多个则分为多行，按字典序排序。

Sample Input 1

1 1A2BD3G4H56JK 23EFG4I5J6K7

Sample Output 1

23G456K 23G45JK

    使用动态规划寻找2个字符串的最长公共序列，这个问题我的博客其他文章（dp小试）有详细说明，就不具体说了，主要是写一下递归打印的方法。

 

 

package test; import java.util.*; public class Main { static Scanner in = new Scanner(System.in); static int maxLen; public static void main(String[] args) { int t = in.nextInt(); while(t-- > 0) { String str1 = in.next(); String str2 = in.next(); slove(str1, str2); } } public static void slove(String str1, String str2) { int[][] dp = new int[str1.length()+1][str2.length()+1]; maxLen = 0; for(int i=1; i<str1.length()+1; i++) { for(int j=1; j<str2.length()+1;j++) { if(str1.charAt(i-1) == str2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } if(dp[i][j] > maxLen) { maxLen = dp[i][j]; } } } // System.out.println("lenth: " + maxLen); List<String> maxFlag = new ArrayList<>();//标记最大长度的位置 String flag; for(int i=1; i<str1.length()+1; i++) { for(int j=1; j<str2.length()+1;j++) { if(dp[i][j] == maxLen) { flag = String.valueOf(i) + " " +String.valueOf(j); maxFlag.add(flag); } } } List<String> list = new ArrayList<>(); for(int f=0; f<maxFlag.size(); f++) { String[] tip = maxFlag.get(f).split(" "); int i = Integer.valueOf(tip[0]); int j = Integer.valueOf(tip[1]); // System.out.println(i+" "+j); String item = ""; findStr(list, dp, str1, str2, i, j, item); } Collections.sort(list); for(int i=0; i<list.size(); i++) { System.out.println(list.get(i)); } } public static void findStr(List<String> list, int[][] count, String str1, String str2, int i, int j, String item) { if(item.length()== maxLen) { if(list.indexOf(item) == -1)//防止重复 list.add(item); return; } // if(i==0 || j==0) { System.out.println(item); // if(list.indexOf(item) == -1)//防止重复 // list.add(item); // return; // } else { if(str1.charAt(i-1) == str2.charAt(j-1)) {//相等追加 String string = str1.charAt(i-1) + item; findStr(list, count, str1, str2, i-1, j-1, string); } else if(count[i-1][j] > count[i][j-1]){//继续寻找次长的，次次长的等等.... findStr(list, count, str1, str2, i-1, j, item); } else if(count[i-1][j] < count[i][j-1]) {//同上 findStr(list, count, str1, str2, i, j-1, item); } else {//(i-1,j)==(i,j-1)等长的话2个都要尝试 findStr(list, count, str1, str2, i-1, j, item); findStr(list, count, str1, str2, i, j-1, item); } } } }

 补上我写的另一个版本，挺简单的，但是不过，我试了很多情况都是对的，我也找不到反例。。。，可能某个点没有考虑到，谁找到了希望能说一下

import java.util.*; public class Main { static Scanner in = new Scanner(System.in); static int N = 1000 + 5; static int[][] dp = new int[N][N]; static String s1, s2; static int a, b, len, cnt = 0; static char[] res = new char[N]; static ArrayList<String> st = new ArrayList<>(); static void init() {// 初始化 st.clear(); cnt = 0; for (int i = 0; i <= a; i++) for (int j = 0; j <= b; j++) dp[i][j] = 0; Arrays.fill(res, ' '); } // 获取指定位数的随机字符串(包含小写字母、大写字母、数字,0<length) static String getRandomString(int length) { // 随机字符串的随机字符库 String KeyString = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; StringBuffer sb = new StringBuffer(); int len = KeyString.length(); for (int i = 0; i < length; i++) { sb.append(KeyString.charAt((int) Math.round(Math.random() * (len - 1)))); } return sb.toString(); } static void slove(int pos, int pre) { if (cnt == len) {// 递归出口，长度达到了最大值 if (st.indexOf(new String(res)) == -1)// 去重 st.add(new String(res)); return; } for (int i = pos; i <= a; i++) { for (int j = 1; j <= b; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) { int temp = pre;// 记录此时的索引值 if (j - 1 > pre) {// 即，保证生成的子序列和在原序列里面的状态一致 res[cnt] = s1.charAt(i - 1); cnt++; pre = j - 1; slove(i + 1, pre);// 回溯 res[cnt] = ' '; cnt--; pre = temp; } } } } } public static void main(String[] args) { int t = in.nextInt(); while (t-- > 0) { init(); s1 = in.next(); s2 = in.next(); // s1 = getRandomString(10); // s2 = getRandomString(15); System.out.println(s1+" "+s2); a = s1.length(); b = s2.length(); for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } len = dp[a][b]; // System.out.println(dp[a][b]); slove(1, -1); if (st.size() != 0) { Collections.sort(st); for (int i = 0; i < st.size(); i++) { System.out.println(st.get(i)); } } } in.close(); } }

 一样的递归输出，但是不过，太难了我，找到bug的call我啊啊啊啊