Take the 2-minute tour ×

As a novice in Python, I have written a working function that will compare two strings and search for the longest substring shared by both strings. For instance, when the function compares "goggle" and "google", it will identify "go" and "gle" as the two common substrings (excluding single letters), but will only return "gle" since it's the longest one.

I would like to know if anywhere part of my code can be improved/re-written, as it may be considered lengthy and convoluted. I'll also be very glad to see other approaches to the solution. Thanks in advance!

def longsub(string1, string2):
    sublist = []

    while i < len(string1):
        while j < len(string2):
            if string1[i:a+1] == string2[j:b+1] and (a+1) <= len(string1) and (b+1) <= len(string2):
                if count > 0:
                count = 0

    while len(sublist) > 1:
        for each in sublist:
            if len(each) >= length:
                length = len(each)

    return sublist[0]

Edit: Comparing "goggle" and "google" may have been a bad example, since they are equal length with longest common segments in the same positions. The actual inputs would be closer to this: "xabcdkejp" and "zkdieaboabcd". Correct output should be "abcd".

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

There actually happens to be a function for this in the standard library: difflib.SequencMatcher.find_longest_match

share|improve this answer
I don't have time to write up an example now, but the docs are pretty clear. After I get back from lunch I'll try to remember to add an example (unless someone else wants to edit one in first [hint hint]) –  mgilson Mar 19 '13 at 16:45
It looks like SamiN has provided an example so I don't have to :) –  mgilson Mar 19 '13 at 17:42
thanks! i'll definitely take a look at that function! :) –  peianwu Mar 20 '13 at 1:05
add comment

EDIT: This algorithm only works when the words have the longest segment in the same indices

You can get away with only one loop. Use helper variables. Something like these (needs refactoring) http://codepad.org/qErRBPav:

word1 = "google"
word2 = "goggle"

longestSegment = ""
tempSegment = ""

for i in range(len(word1)):
    if word1[i] == word2[i]:
        tempSegment += word1[i]
    else: tempSegment = ""

    if len(tempSegment) > len(longestSegment):
        longestSegment = tempSegment

print longestSegment # "gle"

EDIT: mgilson's proposal of using find_longest_match (works for varying positions of the segments):

from difflib import SequenceMatcher

word1 = "google"
word2 = "goggle"

s = SequenceMatcher(None, word1, word2)
match = s.find_longest_match(0, len(word1), 0, len(word2))

print word1[match.a:(match.b+match.size)] # "gle"
share|improve this answer
thank you so much, it's so much simpler and intuitive. thanks! –  peianwu Mar 20 '13 at 1:03
As a side note, I don't think your first solution actually works. For example take the too words: 'google' and 'gleblh'. The longest common substring is gle, but I don't think your function will pick that up. –  mgilson Mar 20 '13 at 1:07
Hi Sami, what if the two strings are a little more scrambled, how would you change your code to reflect that? sorry for not clarifying that, since that's why i resorted to slicing in my own code. –  peianwu Mar 20 '13 at 2:19
Indeed, Mgilson is right. My bad. Will edit the post. –  Sami N Mar 20 '13 at 5:59
In the meantime, I suggest to take a look at the source code of find_longest_match. –  Sami N Mar 20 '13 at 6:14
add comment

Your Answer


