查找两个字符串之间的公共子字符串 [英] Find common substring between two strings
问题描述
我想比较2个字符串并保持匹配,在比较失败的地方分开。
I'd like to compare 2 strings and keep the matched, splitting off where the comparison fails.
所以,如果我有2个字符串-
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
我敢肯定有一种简单的Python方式可以做到这一点,但我无法解决,
I'm sure there is a simple Python way of doing this but I can't work it out, any help and explanation appreciated.
推荐答案
它称为最长公共子字符串问题。在这里,我提出了一个简单,易于理解但效率低下的解决方案。为大型字符串生成正确的输出将花费很长时间,因为该算法的复杂度为O(N ^ 2)。
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")
输出
apple pie
apples
apples
这篇关于查找两个字符串之间的公共子字符串的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!