Find the longest common subsequence algorithm - low speed

Question

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')
xstr = file1.read()
ystr = file2.read()

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')
xstr = file1.read()
ystr = file2.read()

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

Answer 1

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.