'Longest common substring of two strings
Python beginner here and I am trying to make a program that outputs the longest common substring of two strings from the input.
Example:
word1 = input('Give 1. word: xlaqseabcitt')
word2 = input('Give 2. word: peoritabcpeor')
Wanted output:
abc
I have code like this so far:
word1 = input("Give 1. word: ")
word2 = input("Give 2. word: ")
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)
I end up with IndexError when word2 is shorter than word1 and it does not give me the common substring.
Any advice?
Thanks for the help!
EDIT: I found this solution:
string1 = input('Give 1. word: ')
string2 = input('Give 2. word: ')
answer = ""
len1, len2 = len(string1), len(string2)
for i in range(len1):
for j in range(len2):
lcs_temp=0
match=''
while ((i+lcs_temp < len1) and (j+lcs_temp<len2) and string1[i+lcs_temp] == string2[j+lcs_temp]):
match += string2[j+lcs_temp]
lcs_temp+=1
if (len(match) > len(answer)):
answer = match
print(answer)
Is there any way to make this code more clear and suitable for beginners?
Solution 1:[1]
You can build a dictionary from the first string containing the positions of each character, keyed on the characters. Then go through the second string and compare the substring of each character with the rest of the second string at that position:
# extract common prefix
def common(A,B) :
firstDiff = (i for i,(a,b) in enumerate(zip(A,B)) if a!=b) # 1st difference
commonLen = next(firstDiff,min(len(A),len(B))) # common length
return A[:commonLen]
word1 = "xlaqseabcitt"
word2 = "peoritabcpeor"
# position(s) of each character in word1
sub1 = dict()
for i,c in enumerate(word1): sub1.setdefault(c,[]).append(i)
# maximum (by length) of common prefixes from matching first characters
maxSub = max((common(word2[i:],word1[j:])
for i,c in enumerate(word2)
for j in sub1.get(c,[])),key=len)
print(maxSub) # abc
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|---|
Solution 1 |