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

Question

我想比较2个字符串并保持匹配，在比较失败的地方分开。因此，如果我有2个字符串-string1 = applesstring2 = applesesanswer = apples另一个示例，因为字符串可以有多个单词。string1 = apple pie availablestring2 = apple piesanswer = apple pie我敢肯定有一种简单的Python方式可以做到这一点，但我无法解决，感谢任何帮助和解释。

Answer 1

它称为最长公共子串问题。在这里，我提出了一个简单，易于理解但效率低下的解决方案。为大型字符串生成正确的输出将花费很长时间，因为该算法的复杂度为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

Answer 2

为了完整起见，difflib在标准库中提供了许多序列比较实用程序。例如find_longest_match，当在字符串上使用时，它会找到最长的公共子字符串。使用示例：

from difflib import SequenceMatcher

string1 = "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)  # -> Match(a=0, b=15, size=9)

print(string1[match.a: match.a + match.size])  # -> apple pie

print(string2[match.b: match.b + match.size])  # -> apple pie