0

次の I/O を行う LCS のバージョンを実装するとします。

入力: superLCS('猫','車')

出力: ['ca#','ca#']

現在、私のプログラムはそのために機能しますが、文字がずれていると機能しません。

たとえば、入力が superLCS('art','cad') の場合、出力は ['###','###'] になります。['a##','##a#'] が出力されているはずです

コード：

def superLCS(s1,s2):
    return helper(s1,s2,'','')

def helper(s1,s2,res1,res2):  #s1 is string 1, s2 is string 2, res1 is result1, res2 is result2
    if s1 == '' or s2 == '': #if either string is empty return the result
        return [res1,res2]
    if s1[0] == s2[0]: #if they are equal, put their string in the list
        res1 += s1[0]
        res2 += s1[0]
        return helper(s1[1:],s2[1:],res1,res2)
    else:  #if they arent, add a # to the list
        res2 += '#'
        res1 += '#'
        return helper(s1[1:],s2[1:],res1,res2)
4

1 に答える 1

0

あなたの問題はアルゴリズムです。LCS は古典的な動的計画法アルゴリズムであり、次元の「行列」を埋める必要がありますlen(s1) x len(s2)。各値は、その上のセルの値、その左のセル、およびその斜め上の左M[i,j]のセルの値に依存します。これは次のとおりです。 LCSの長さを取得するだけです。(潜在的な LCS の 1 つ) を取得するには、右下隅から左上への追加の「トレースバック」を行う必要があります。M[i-1,j]M[i,j-1]M[i-1][j-1]

これを行っていないため、サブシーケンスのスペースをより単純で狭い検索を行っているため、2 番目の例では正しい LCS が見つかりません。

これはすべて、ウィキペディアでかなりうまく説明および実証されています。

于 2012-09-22T16:15:18.797 に答える