# Find the longest common subsequence algorithm - low speed

I've designed an algorithm to find the longest common subsequence.

These are steps:

• Pick the first letter in the first string.

• Look for it in the second string and if its found, Add that letter to common_subsequence and store its position in index, Otherwise compare the length of common_subsequence with the length of lcs and if its greater, asign its value to lcs.

• Return to the first string and pick the next letter and repeat the previous step again, But this time start searching from indexth letter

• Repeat this process until there is no letter in the first string to pick. At the end the value of lcs is the Longest Common Subsequence.

This is an example:

X=A, B, C, B, D, A, B‬‬
‫‪Y=B, D, C, A, B, A‬‬

1. Pick A in the first string.
2. Look for A in Y.
3. Now that there is an A in the second string, append it to common_subsequence.
4. Return to the first string and pick the next letter that is B.
5. Look for B in the second string this time starting from the position of A.
6. There is a B after A so append B to common_subsequence.
7. Now pick the next letter in the first string that is C. There isn't a C next to B in the second string. So assign the value of common_subsequence to lcs because its length is greater than the length of lcs.

Repeat the previous steps until reaching the end of the first string. In the end the value of lcs is the Longest Common Subsequence.

The complexity of this algorithm is $\theta(n*m)$.

I implemented it on two methods. The second one is using a hash table, but after implementation I found it's much slower compared to the first algorithm. I can't understand why.

The first algorithm:

import time
def lcs(xstr, ystr):
if not (xstr and ystr): return # if string is empty
lcs = [''] #  longest common subsequence
lcslen = 0 # length of longest common subsequence so far
for i in xrange(len(xstr)):
cs = '' # common subsequence
start = 0 # start position in ystr
for item in xstr[i:]:
index = ystr.find(item, start) # position at the common letter
if index != -1: # if common letter is found
cs += item # add common letter to the cs
start = index + 1
if index == len(ystr) - 1: break # if reached to the end of ystr
# updates lcs and lcslen if found better cs
if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
elif len(cs) == lcslen: lcs.append(cs)
return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed


The second one using hash table:

import time
from collections import defaultdict
def lcs(xstr, ystr):
if not (xstr and ystr): return # if strings are empty
lcs = [''] #  longest common subsequence
lcslen = 0 # length of longest common subsequence so far
location = defaultdict(list) # keeps track of items in the ystr
i = 0
for k in ystr:
location[k].append(i)
i += 1
for i in xrange(len(xstr)):
cs = '' # common subsequence
index = -1
reached_index = defaultdict(int)
for item in xstr[i:]:
for new_index in location[item][reached_index[item]:]:
reached_index[item] += 1
if index < new_index:
cs += item # add item to the cs
index = new_index
break
if index == len(ystr) - 1: break # if reached to the end of ystr
# update lcs and lcslen if found better cs
if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
elif len(cs) == lcslen: lcs.append(cs)
return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

-

Firstly, your algorithm is incorrect try:

lcs("AAAABCC","AAAACCB"), the LCS should be "AAAACC", but your algorithm finds "AAAAB".

Secondly your algorithm is O(n^2*m) not O(n*m). Since you don't elaborate as to why you think your algorithm is theta(n*m) I can't really guess where your analysis has gone wrong.

Your second version attempts to optimize the process of searching through the string by using a list of pre-calculated positions. This means you don't have to scan through all the positions in the string with different characters. However, you lose the ability to skip all the position before your starting index. For long strings with few distinct characters, you end up losing out.

-
I made a little changes to my algorithm. now it passes your test case. i uploaded it here: pastebin.com/030Uhpcr .the only change that i made is that it calls the function two time. first lcs(xstr, ystr) and second lcs(ystr, xstr). but i still think that its complexity is theta(n*m). because it loops through second string n times. –  Sajjad Rastegar Jan 10 '13 at 13:46
@Rastegar, your algorithm is still incorrect, try: "AAAABCCD" and "AAAADCCB". As for complexity, ystr.find is called n*(n/2) times, or O(n^2). The complexity of ystr.find is O(m), thus the cost is O(n^2*m). It doesn't loop through the second string m times, because you've got two nested for loops there, not one. –  Winston Ewert Jan 10 '13 at 14:14
Ok, It seems that my program certainly made fail. but it's complexity was theta(n*m) becuase ystr.find(item, start) doesn't start searching from the beginning of the list but it starts from start where it found the common letter in the last searching. and after getting the end of ystr, exits from the second loop. –  Sajjad Rastegar Jan 10 '13 at 15:55
@Rastegar, ok I missed a subtlety in your algorithm. I thought start was being reset more then it was. So yes it appears to be theta(n*m) but that's all moot because it doesn't work. –  Winston Ewert Jan 10 '13 at 18:11