Finding the longest substring in common with two large strings

Question

I want to build a function which finds the longest substring that is common between two large strings. I want to do this using the first two functions. I'm running it on very large strings (containing more than million characters) and it's taking a lot of time. How can I optimize the function findlongest?

def hash_sequence(string, k):

    dictionary={}
    for i in range(len(string)-(k-1)):
        sequence = string[i:i+k]
        dictionary.setdefault(sequence,[]).append(i)
    return dictionary



def intersects(string1, string2, k): #what if k=0?
    dictionary = hash_sequence(string1, k)

    for i in range(len(string2)-1): #O(n) for sybstring in string

        if string2[i:i+k] in dictionary: #O(n
            return string2[i:i+k]
    return None

def findlongest(string1,string2):
    if intersects(string1,string2,1)==None:
        return None
    for i in range(2,min(len(string1),len(string2))):

        if intersects(string1,string2,i)==None:
            return intersects(string1,string2,i-1),len(intersects(string1,string2,i-1))

Answer 1

One big problem is that when you reach the longest common sequence and are ready to return, you re-run the previous iteration twice. Variables are your friends:

def find_longest(string1, string2):
    longest_seq = None

    for i in range(1, min(len(string1), len(string2))):
        # Store the current iteration's intersection
        current_seq = intersects(string1, string2, i)

        # If this was one character too long, return.
        # Else, a longer intersection was found. Store it.
        if current_seq == None:
            return longest_seq, i-1
        else:
            longest_seq = current_seq

    # If we get here, the strings were the same.
    # For consistency, return longest_seq and its length.
    return longest_seq, len(longest_seq)

By adding in the two variables, we were able to remove the if-statement at the beginning and now only have to call intersects() once in the for-loop.

Also, take a look at PEP8, the official Python style guide. It will help you fit Pythonic conventions more closely.

---

If you wanted to use a more complex, and quite possibly faster, solution, take a look into implementing a binary search algorithm. They provide search times that are very efficient for large data sets.

Answer 2

Why don't you use the dynamic programming version of the code. Its complexity is O(nm) where n and m are the lengths of two strings. Yours seem to be a lot more complicated one. Below is a python code which implements the O(nm) solution of the problem.

def LCS(stringA, stringB):
lenStringA = 1 + len(stringA)
lenStringB = 1 + len(stringB)

matrix = [[0] * (lenStringB) for i in range(lenStringA)]

substringLength = 0
endIndex = 0

for aIndex in range(1, lenStringA):
    for bIndex in range(1, lenStringB):

        if stringA[aIndex - 1] == stringB[bIndex - 1]:

            matrix[aIndex][bIndex] = matrix[aIndex - 1][bIndex - 1] + 1

            if matrix[aIndex][bIndex] > substringLength:

                substringLength = matrix[aIndex][bIndex]
                endIndex = aIndex

        else:

            matrix[aIndex][bIndex] = 0

return stringA[endIndex - substringLength: endIndex]