Longest Common Substring: recursive solution?
Try to avoid any confusion, what you're asking is longest common substring
, not longest common subsequence
, they're quite similar but have differences.
The recursive method for finding longest common substring is:
Given A and B as two strings, let m as the last index for A, n as the last index for B.
if A[m] == B[n] increase the result by 1.
if A[m] != B[n] :
compare with A[m -1] and B[n] or
compare with A[m] and B[n -1]
with result reset to 0.
The following is the code without applying memoization for better illustrating the algorithm.
public int lcs(int[] A, int[] B, int m, int n, int res) {
if (m == -1 || n == -1) {
return res;
}
if (A[m] == B[n]) {
res = lcs(A, B, m - 1, n - 1, res + 1);
}
return max(res, max(lcs(A, B, m, n - 1, 0), lcs(A, B, m - 1, n, 0)));
}
public int longestCommonSubString(int[] A, int[] B) {
return lcs(A, B, A.length - 1, B.length - 1, 0);
}
package algo.dynamic;
public class LongestCommonSubstring {
public static void main(String[] args) {
String a = "LABFQDB";
String b = "LABDB";
int maxLcs = lcs(a.toCharArray(), b.toCharArray(), a.length(), b.length(), 0);
System.out.println(maxLcs);
}
private static int lcs(char[] a, char[] b, int i, int j, int count) {
if (i == 0 || j == 0)
return count;
if (a[i - 1] == b[j - 1]) {
count = lcs(a, b, i - 1, j - 1, count + 1);
}
count = Math.max(count, Math.max(lcs(a, b, i, j - 1, 0), lcs(a, b, i - 1, j, 0)));
return count;
}
}
Here is the recursive code for LONGEST COMMON SUBSTRING:
int LCS(string str1, string str2, int n, int m, int count)
{
if (n==0 || m==0)
return count;
if (str1[n-1] == str2[m-1])
return LCS(str1, str2, n-1, m-1, count+1);
return max(count, max(LCS(str1, str2, n-1, m, 0), LCS(str1, str2, n, m-1, 0)));
}