Python は初めてのプログラミング言語で、手動でデータ構造を操作して遊んでみたいと思っていました。
私は最近、LCS問題を解決するための基本的なアルゴリズムを学んでおり、奇妙な理由で完全に把握していると自分自身を納得させることができない1行のコード以外に、それがどのように機能するかを理解しています。
これは、自分でうまく理解できなかった後、学ぶために使用してきたコードです。
編集 2:とにかく、整数の 2 つのリストの入力でこれを機能させるには? **元の質問を正しく理解していることがわかりましたが、**整数のリストでこれを機能させる方法を知っている人はいますか? S と T をカンマ区切りの値の文字列に変換してみましたが、これは一部の文字の一致に機能しましたが、それでもほとんどのテストケースではほとんど機能しませんでした。比較されるのは 2 つの文字列だけですが、コンマが含まれているため、なぜそうならないのかわかりません。
def lcs(S,T):
m = len(S)
n = len(T)
counter = [[0]*(n+1) for x in range(m+1)]
longest = 0
lcs_set = set()
for i in range(m):
for j in range(n):
if S[i] == T[j]:
c = counter[i][j] + 1
counter[i+1][j+1] = c
if c > longest:
lcs_set = set()
longest = c
lcs_set.add(S[i-c+1:i+1])
elif c == longest:
lcs_set.add(S[i-c+1:i+1])
return lcs_set
今、私の問題は次の行を理解することです: lcs_set.add(S[i-c+1:i-1])
部分文字列の長さを最長にするために、一致が見つかったときにカウンターがインクリメントされることを理解しています。したがって、簡単にするために、S = Crow で T = Crown の場合、最後の一致である w に到達すると、カウンターは 4 にインクリメントされ、i は S のインデックス 3 になります。
これは、次のように読むことを意味しますか: i (S のインデックス 3、W) - c (4)、つまり 3-4 = -1、つまり 3-4+1 = 0 (C で) と右側の場合スライスの: i(3) + 1 = 4(N、しかし明らかに含まれません)、つまり、S[0:4]、Crow、LCS_Setで終了しますか?
その場合、最新の一致した文字だけでなく、部分文字列全体をセットに追加する理由について混乱していると思いますか?
私が正しく理解している場合、現在一致している部分文字列のスライス全体でLCS_setを更新しているため、2 番目の一致である R の場合、カウンターは 2 になり、i は 1 になり、S[ となります。 1-2+1:i(1)+1]、したがって 1-2 = -1、-1 + 1 = 0(C) i(1)+1 = 2 まで (S[0:2 を残す) ]、または CR) であるため、毎回、セットは現在のインデックスだけでなく、部分文字列全体で更新されます。
それは実際には問題ではありません。これを正しく理解していることを確認したいだけです。
意見や、現在のロジックで誰かが見るかもしれないヒントをいただければ幸いです!!
編集：
Cの位置が現在のカウンター番号であることを完全に忘れていたことに気付きました。したがって、明らかに現在の最大一致番号でLCS_setを更新することはなく、現在の一致文字だけで更新することはできません。 LCS_Set を更新するには、部分文字列のスライスを取得する必要があります。前もって感謝します！