Blogs Hub

by AskGif | Jul 30, 2018 | Category :coding

How to Find Longest Common Subsequence ?

How to Find Longest Common Subsequence ?

<p>The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.</p> <p>&nbsp;</p> <p>Recursive Solution :</p> <pre class="language-java"><code>package dp; public class LCS { public static int max(int a, int b) { return a&gt;b?a:b; } public static int LCSUtil(String str1, int i, int len1, String str2, int j, int len2) { if(i == len1 || j == len2) return 0; if(str1.charAt(i)==str2.charAt(j)) return 1 + LCSUtil(str1, i+1, len1, str2, j+1, len2); return max(LCSUtil(str1, i+1, len1, str2, j, len2), LCSUtil(str1, i, len1, str2, j+1, len2)); } public static int FindLCS(String str1, String str2) { return LCSUtil(str1,0,str1.length(),str2,0,str2.length()); } public static void main(String[] args) { String str1 = "ABCBDAB"; String str2 = "BDCABA"; long startTime = System.nanoTime(); System.out.println(FindLCS(str1,str2)); long endTime = System.nanoTime(); long totalTime = endTime - startTime; System.out.println("Total Time (nanoseconds) : " + (totalTime)); } } </code></pre> <pre class="language-markup"><code>output: 4 Total Time (nanoseconds) : 894489 </code></pre> <p>This is a correct solution but it is very time-consuming. The time complexity of the above solution is O(2^n).</p> <p>&nbsp;</p> <p>Now We will solve this question using Dynamic Programming by using Memoization:</p> <pre class="language-java"><code>package dp; public class LCS { public static int max(int a, int b) { return a&gt;b?a:b; } public static int LCSUtil(String str1, int i, int len1, String str2, int j, int len2) { int[][] dp = new int[len1+1][len2+1]; for(int x=0;x&lt;len1;x++) dp[x][len2]=0; for(int x=0;x&lt;len2;x++) dp[len1][x]=0; for(int x=len1-1;x&gt;=0;x--) { for(int y=len2-1;y&gt;=0;y--) { dp[x][y]=dp[x+1][y+1]; if(str1.charAt(x)==str2.charAt(y)) { dp[x][y]++; } if(dp[x+1][y]&gt;dp[x][y]) dp[x][y]=dp[x+1][y]; if(dp[x][y+1]&gt;dp[x][y]) dp[x][y]=dp[x][y+1]; } } return dp[0][0]; } public static int FindLCS(String str1, String str2) { return LCSUtil(str1,0,str1.length(),str2,0,str2.length()); } public static void main(String[] args) { String str1 = "ABCBDAB"; String str2 = "BDCABA"; long startTime = System.nanoTime(); System.out.println(FindLCS(str1,str2)); long endTime = System.nanoTime(); long totalTime = endTime - startTime; System.out.println("Total Time (nanoseconds) : " + (totalTime)); } } </code></pre> <pre class="language-markup"><code>output: 4 Total Time (nanoseconds) : 275257 </code></pre> <p>The time complexity of the above solution is O(mn). Where m and n are the length of two strings to be compared.</p> <p>&nbsp;</p>

read more...