输入两句话，求最大子序列
package D3_12; import java.util.Scanner; public class ZiXuLie { static String[] sen1; static String[] sen2; static int[][] p; static StringBuilder result; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) {// 注意多组输入 result = new StringBuilder(); // ------------------输入并分割语句--------------------- StringBuilder sb = new StringBuilder(); String str; String tmp; while (true) { tmp = sc.nextLine(); if (tmp.endsWith("#")) { tmp = tmp.substring(0, tmp.length() - 1); sb.append(tmp); break; } sb.append(tmp + "\n"); } str = sb.toString(); sen1 = str.split("\\s+|\\n"); sb = new StringBuilder(); while (true) { tmp = sc.nextLine(); if (tmp.endsWith("#")) { tmp = tmp.substring(0, tmp.length() - 1); sb.append(tmp); break; } sb.append(tmp + "\n"); } str = sb.toString(); sen2 = str.split("\\s+|\\n"); // ----------------------------------------------------------- int[][] c = new int[sen1.length + 2][sen2.length + 2];// 图形记录 p = new int[sen1.length + 2][sen2.length + 2];// 记录行走方向 for (int i = 1; i <= sen1.length; i++) { for (int j = 1; j <= sen2.length; j++) { if (sen1[i - 1].equals(sen2[j - 1])) { c[i][j] = c[i - 1][j - 1] + 1; p[i][j] = 1; } else if (c[i - 1][j] >= c[i][j - 1]) {// 单词不同的话舍掉哪个都一样(向下走或者向右走，这里默认向下走) p[i][j] = 2; c[i][j] = c[i - 1][j]; } else { p[i][j] = 3; c[i][j] = c[i][j - 1]; } } } print(sen1.length, sen2.length); System.out.println(result.substring(0, result.length() - 1)); } } // 递归打印 static void print(int i, int j) { if (i == 0 || j == 0) return; if (p[i][j] == 1) { print(i - 1, j - 1); result.append(sen1[i - 1] + " "); } else if (p[i][j] == 2) { print(i - 1, j); } else if (p[i][j] == 3) { print(i, j - 1); } } }