public class q2{
public static void main(String[] args) {
String S1 = “ACCCGTCGAGTGCGCGCGGAAGCCGGCCG”;
String S2 = “GTCGTTCGGAATGCCGTTGCTCTGTAAA”;
String lcs = longestCommonSubsequence(S1, S2);
System.out.println(“Longest Common Subsequence: “ + lcs);
}
public static String longestCommonSubsequence(String S1, String S2) {
int m = S1.length();
int n = S2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else 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]);
}
}
}
StringBuilder lcs = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (S1.charAt(i – 1) == S2.charAt(j – 1)) {
lcs.insert(0, S1.charAt(i – 1));
i–;
j–;
} else if (dp[i – 1][j] > dp[i][j – 1]) {
i–;
} else {
j–;
}
}
return lcs.toString();
}
}
