[解決済み] 2つの文字列の間にある共通の部分文字列を検索する

質問

2つの文字列を比較して、一致したものを残し、比較に失敗したものを分割して表示したい。

2つの文字列があった場合

string1 = apples
string2 = appleses

answer = apples

文字列が複数の単語を持つ可能性があるため、別の例を示します。

string1 = apple pie available
string2 = apple pies

answer = apple pie

私はこれを行うには、単純なPythonの方法があると確信していますが、私はそれを解決することはできません、任意のヘルプと説明をお願いします。

どのように解決するのですか？

Longest Common Substring問題と呼ばれるものです。ここでは、単純で理解しやすいが非効率的な解決策を紹介します。このアルゴリズムの複雑さは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