1

2 つの文字列の最長の共通サブシーケンスを見つけるために、これらの関数 (動作する) を作成しました。

def lcs_grid(xs, ys):
    grid = defaultdict(lambda: defaultdict(lambda: (0,"")))
    for i,x in enumerate(xs):
        for j,y in enumerate(ys):
            if x == y:
                grid[i][j] = (grid[i-1][j-1][0]+1,'\\')
            else:
                if grid[i-1][j][0] > grid[i][j-1][0]:
                    grid[i][j] = (grid[i-1][j][0],'<')
                else:
                    grid[i][j] = (grid[i][j-1][0],'^')

    return grid

def lcs(xs,ys):
    grid = lcs_grid(xs,ys)
    i, j = len(xs) - 1, len(ys) - 1

    best = []
    length,move = grid[i][j]
    while length:
        if move == '\\':
            best.append(xs[i])
            i -= 1
            j -= 1
        elif move == '^':
            j -= 1
        elif move == '<':
            i -= 1
        length,move = grid[i][j]

    best.reverse()
    return best

関数 st を変更して、3 つの文字列の最長の共通サブシーケンスを出力できるという提案はありますか? つまり、関数呼び出しは次のようになります。lcs(str1, str2, str3)

今まではreduce文でなんとかしていたのですが、reduce文なしで本当にサブシーケンスを出力する関数が欲しいです。

4

1 に答える 1

6

D 文字列の最長共通部分文字列を見つけるために、単純に を使用することはできませんreduce。これは、3 つの文字列の最長共通部分文字列が 2 つのいずれかの LCS の部分文字列である必要がないためです。反例:

a = "aaabb"
b = "aaajbb"
c = "cccbb"

例では、LCS(a,b) = "aaa" および LCS(a, b, c) = "bb" です。ご覧のとおり、「bb」は「aaa」の部分文字列ではありません。

あなたの場合、動的計画法のバージョンを実装したので、D 次元グリッドを構築し、それに応じてアルゴリズムを調整する必要があります。

物事をより速くするための接尾辞ツリーを見たいと思うかもしれません.ウィキペディアを参照してください. このスタックオーバーフローの質問も見てください

于 2012-05-24T23:00:45.937 に答える