package com.pap.base.util.string;
public class LongestCommonSubsequence {
public static void main(String[] args) { String str1 = "ABCBDAB"; String str2 = "BDCAB";
int[][] dp = computeLCS(str1, str2);
String lcs = findLCS(dp, str1, str2);
System.out.println("Longest Common Subsequence: " + lcs); System.out.println("Positions in String-1 : " + getLCSPositions(dp, str1, lcs)); System.out.println("Positions in String-2 : " + getLCSPositions(dp, str2, lcs)); }
private static int[][] computeLCS(String str1, String str2) { int m = str1.length(); int n = str2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; 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]); } } }
return dp; }
private static String findLCS(int[][] dp, String str1, String str2) { int m = str1.length(); int n = str2.length();
StringBuilder lcs = new StringBuilder(); int i = m, j = n;
while (i > 0 && j > 0) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { lcs.insert(0, str1.charAt(i - 1)); i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } }
return lcs.toString(); }
private static String getLCSPositions(int[][] dp, String str, String lcs) { StringBuilder positions = new StringBuilder(); int i = 1, j = 1;
for (char c : lcs.toCharArray()) { while (i <= str.length() && str.charAt(i - 1) != c) { i++; }
positions.append(i).append(" "); i++; }
return positions.toString().trim(); }}
评论