Find common substring between two strings

Question

I'd like to compare 2 strings and keep the matched, splitting off where the comparison fails.

So if I have 2 strings:

string1 = "apples"
string2 = "appleses"

answer = "apples"

Another example, as the string could have more than one word:

string1 = "apple pie available"
string2 = "apple pies"

answer = "apple pie"

I'm sure there is a simple Python way of doing this but I can't work it out, any help and explanation appreciated.

Answer 1

Its called Longest Common Substring problem. Here I present a simple, easy to understand but inefficient solution. It will take a long time to produce correct output for large strings, as the complexity of this algorithm is O(N^2).

def longestSubstringFinder(string1, string2):
    answer = ""
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        match = ""
        for j in range(len2):
            if (i + j < len1 and string1[i + j] == string2[j]):
                match += string2[j]
            else:
                if (len(match) > len(answer)): answer = match
                match = ""
    return answer

print(longestSubstringFinder("apple pie available", "apple pies"))
print(longestSubstringFinder("apples", "appleses"))
print(longestSubstringFinder("bapples", "cappleses"))

Output

apple pie
apples
apples