Don't like ads? PRO users don't see any ads ;-)

# Untitled

By: a guest on May 5th, 2012  |  syntax: None  |  size: 0.84 KB  |  hits: 9  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. How to find the Longest Common Subsequence in Exponential time?
2. def lcs(s1, s2):
3.  if len(s1)==0 or len(s2)==0: return 0
4.  if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:])
5.  return max(lcs(s1, s2[1:]), lcs(s1[1:], s2))
6.
7. for i=n to 0
8.     for all length i subsequences s of a
9.         if s is a subsequence of b
10.             return s
11.
12. def common_subsequences(A,B, len_subsequence_so_far = 0):
13.     if len(A) == 0 or len(B) == 0:
14.         return
15.     first_of_A = A[0] // the first letter in A.
16.     A1 = A[1:] // A, but with the first letter removed
17.     common_subsequences(A1,B,len_subsequence_so_far) // the first recursive call
18.     if(the_first_letter_of_A_is_also_in_B):
19.         Bn = ... delete from the start of B up to, and including,
20.              ... the first letter which equals first_of_A
21.         common_subsequences(A1,Bn, 1+len_subsequence_so_far )