Finding the longest substring in common with two large strings 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))
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.