1

Python の初心者として、2 つの文字列を比較し、両方の文字列が共有する最長の部分文字列を検索する作業関数を作成しました。たとえば、関数が「goggle」と「google」を比較すると、「go」と「gle」が 2 つの共通部分文字列 (1 文字を除く) として識別されますが、「gle」が最も長いため、「gle」のみが返されます。

コードが長くて複雑であると見なされる可能性があるため、コードのどこかを改善/再作成できるかどうかを知りたいです。また、解決策への他のアプローチを見てとてもうれしく思います。前もって感謝します！

def longsub(string1, string2):
    sublist = []
    i=j=a=b=count=length=0

    while i < len(string1):
        while j < len(string2):
            if string1[i:a+1] == string2[j:b+1] and (a+1) <= len(string1) and (b+1) <= len(string2):
                a+=1
                b+=1
                count+=1
            else:
                if count > 0:
                    sublist.append(string1[i:a])
                count = 0
                j+=1
                b=j
                a=i
        j=b=0
        i+=1
        a=i

    while len(sublist) > 1:
        for each in sublist:
            if len(each) >= length:
                length = len(each)
            else:
                sublist.remove(each)

    return sublist[0]

編集: 「ゴーグル」と「グーグル」の比較は、同じ位置にある最長の共通セグメントと同じ長さであるため、悪い例である可能性があります。実際の入力は、「xabcdkejp」と「zkdieaboabcd」に近いものになります。正しい出力は「abcd」です。

4

2 に答える 2

2

EDIT：このアルゴリズムは、単語が同じインデックスに最長のセグメントを持っている場合にのみ機能します

たった1回のループで逃げることができます。ヘルパー変数を使用します。これらのようなもの (リファクタリングが必要) http://codepad.org/qErRBPav :

word1 = "google"
word2 = "goggle"

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 # "gle"

編集:mgilsonの使用の提案find_longest_match(セグメントのさまざまな位置で機能します):

from difflib import SequenceMatcher

word1 = "google"
word2 = "goggle"

s = SequenceMatcher(None, word1, word2)
match = s.find_longest_match(0, len(word1), 0, len(word2))

print word1[match.a:(match.b+match.size)] # "gle"
于 2013-03-19T16:55:35.393 に答える