# [SOLVED] Find common substring between two strings

## Issue

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

``````

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

``````string1 = apple pie available
string2 = apple pies

``````

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

## Solution

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):
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:
match = ""

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

Output

``````apple pie
apples
apples
``````