How to find the longest common subsequence in exponential time?

Question

I can do it right using dynamic programming, but I cannot figure out how to do this in exponential time.

I am looking to find the largest common subsequence between two lines. Note. I mean subsequences, not substrings; the characters that make up a sequence need not be sequential.

Answer 1

Just replace the table lookup in dynamic programming code with recursive calls. In other words, just implement the recursive formulation of the LCS problem:

EDIT

In pseudo code (practically python, actually):

def lcs(s1, s2): if len(s1)==0 or len(s2)==0: return 0 if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:]) return max(lcs(s1, s2[1:]), lcs(s1[1:], s2)) 

Answer 2

Say you have two lines a and b length n . The longest common subsequence will be the longest subsequence in row a , which is also present in row b .

Thus, we can iterate over all possible subsequences in a and see that it is in b .

Under a high level alias for this would be:

 for i=n to 0 for all length i subsequences s of a if s is a subsequence of b return s 

Answer 3

String A and String B. The recursive algorithm may be naive, but it is simple:

Look at the first letter A. It will either be in the general sequence or not. Considering the no, we truncate the first letter and call it recursively. Considering the option “is in the general sequence”, we also cut it off, and we also get off from the beginning of B to and including the same letter in B. Some pseudo-code:

 def common_subsequences(A,B, len_subsequence_so_far = 0): if len(A) == 0 or len(B) == 0: return first_of_A = A[0] // the first letter in A. A1 = A[1:] // A, but with the first letter removed common_subsequences(A1,B,len_subsequence_so_far) // the first recursive call if(the_first_letter_of_A_is_also_in_B): Bn = ... delete from the start of B up to, and including, ... the first letter which equals first_of_A common_subsequences(A1,Bn, 1+len_subsequence_so_far ) 

You can start by doing this and then optimizing by recalling the longest subsequence found so far and then returning earlier when the current function cannot beat it (i.e. when min(len(A), len(B))+len_subsequence_so_far less than the longest length found so far.

Answer 4

Essentially, if you do not use the dynamic programming paradigm, you achieve exponential time. This is because, without storing your partial values, you recalculate the partial values ​​several times.

Answer 5

To achieve exponential time, it is enough to create all subsequences of both arrays and compare them with each other. If you match two that are identical, check to see if their length is longer than the current maximum. The pseudocode will be:

 Generate all subsequences of `array1` and `array2`. for each subsequence of `array1` as s1 for each subsequece of `array2` as s2 if s1 == s2 //check char by char if len(s1) > currentMax currentMax = len(s1) for i = 0; i < 2^2; i++; 

This is absolutely not optimal . He is not even trying. However, the question is a very inefficient algorithm, so I provided it.

Answer 6

 int lcs(char[] x, int i, char[] y, int j) { if (i == 0 || j == 0) return 0; if (x[i - 1] == y[j - 1]) return lcs(x, i - 1, y, j - 1) + 1; return Math.max(lcs(x, i, y, j - 1), lcs(x, i - 1, y, j)); } print(lcs(x, x.length, y, y.length); 

Below is a partial recursion tree:

  lcs("ABCD", "AFDX") / \ lcs("ABC", "AFDX") lcs("ABCD", "AFD") / \ / \ lcs("AB", "AFDX") lcs("AXY", "AFD") lcs("ABC", "AFD") lcs("ABCD", "AF") 

In the worst case, the length of the LCS is 0, which means the absence of a common subsequence. In this case, all possible subsequences are checked and substitutions O(2^n) exist.

Answer 7

I think we can use Dynamic Programming (DP) and compute the longest common subsequence . A full explanation can be found at http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

 #include <iostream> #include <cstring> #define MAX1 1000 #define MAX2 1000 using namespace std; int val[MAX1][MAX2]; int maximum(int x, int y) { if(x>=y) { return x; } else { return y; } } int longestCommonSubsequence_recur(char str1[MAX1], int i, char str2[MAX2], int j) { if(i<0 || j<0 ) { return 0; } else if(val[i][j] != -1) { return val[i][j]; } if(str1[i]==str2[j]) { val[i][j] = 1 + longestCommonSubsequence_recur(str1, i-1, str2, j-1); } else { val[i][j] = maximum(longestCommonSubsequence_recur(str1, i, str2, j-1) , longestCommonSubsequence_recur(str1, i-1, str2, j)); } return val[i][j]; } int main() { int length1, length2, num; char str1[MAX1], str2[MAX2]; cout<<"String 1 : "; cin>>str1; length1 = strlen(str1); cout<<"String 2 : "; cin>>str2; length2 = strlen(str2); // Initialize the Value Array by "-1" for(int i=0; i<length1; i++) { for(int j=0; j<length2; j++) { val[i][j] = -1; } } num = longestCommonSubsequence_recur(str1, length1-1, str2, length2-1); cout<<endl<<num; return 0; }