查找两个字符串之间的公共子字符串

Question

我想比较2个字符串并保持匹配，在比较失败的地方分开。

因此，如果我有2个字符串-

string1 = apples

string2 = appleses

answer = apples

另一个示例，因为字符串可以有多个单词。

string1 = apple pie available

string2 = apple pies

answer = apple pie

我敢肯定有一种简单的Python方式可以做到这一点，但我无法解决，感谢任何帮助和解释。

Answer 1

它称为最长公共子串问题。在这里，我提出了一个简单，易于理解但效率低下的解决方案。为大型字符串生成正确的输出将花费很长时间，因为该算法的复杂度为O（N ^ 2）。def longestSubstringFinder(string1, string2):&nbsp; &nbsp; answer = ""&nbsp; &nbsp; len1, len2 = len(string1), len(string2)&nbsp; &nbsp; for i in range(len1):&nbsp; &nbsp; &nbsp; &nbsp; match = ""&nbsp; &nbsp; &nbsp; &nbsp; for j in range(len2):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i + j < len1 and string1[i + j] == string2[j]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; match += string2[j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (len(match) > len(answer)): answer = match&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; match = ""&nbsp; &nbsp; return answerprint longestSubstringFinder("apple pie available", "apple pies")print longestSubstringFinder("apples", "appleses")print longestSubstringFinder("bapples", "cappleses")产量apple pieapplesapples

Answer 2

为了完整起见，difflib在标准库中提供了许多序列比较实用程序。例如find_longest_match，当在字符串上使用时，它会找到最长的公共子字符串。使用示例：from difflib import SequenceMatcherstring1 = "apple pie available"string2 = "come have some apple pies"match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))print(match)&nbsp; # -> Match(a=0, b=15, size=9)print(string1[match.a: match.a + match.size])&nbsp; # -> apple pieprint(string2[match.b: match.b + match.size])&nbsp; # -> apple pie