3つのシーケンスの中で最も長い共通サブシーケンス

Question

私は3シーケンスの最長共通サブシーケンスのバージョンを実装しており、間違いを見つけることはできません。しかし、Courseraの学年は、私が最後のテストケースに失敗したと言います。 アルゴリズムはほぼ正しいですが、の具体的なのケースでは間違った答えを出力します。しかし、それはどういう場合ですか？

制約事項：リストの長さは1以上100以下です。リスト内の数字は、-10^9〜10^9の整数です。

import sys 


def lcs3(a, b, c): 
    start_b = 0 
    start_c = 0 
    result = [] 
    for i in range(len(a)): 
     for j in range(start_b, len(b)): 
      if a[i] == b[j]: 
       for k in range(start_c, len(c)): 
        if b[j] == c[k]: 
         start_b = j+1 
         start_c = k+1 
         result.append(a[i]) 
         break 
       if b[j] == c[k]: 
        break 
    return len(result) 


def lcs3_reversed(a,b, c): 
    # check reversed sequence which can be with different order 
    a_rev = a[::-1] 
    b_rev = b[::-1] 
    c_rev = c[::-1] 
    result = lcs3(a, b, c) 
    result_reversed = lcs3(a_rev, b_rev, c_rev) 
    if result == result_reversed: 
     return result 
    else: 
     return result_reversed 


if __name__ == '__main__': 
    input = sys.stdin.read() 
    data = list(map(int, input.split())) 
    an = data[0] 
    data = data[1:] 
    a = data[:an] 
    data = data[an:] 
    bn = data[0] 
    data = data[1:] 
    b = data[:bn] 
    data = data[bn:] 
    cn = data[0] 
    data = data[1:] 
    c = data[:cn] 
    print(lcs3_reversed(a, b, c)) 

更新：はがあなたによって記述例を解決するためにをlcs3_reversed機能を追加しました。とにかくテストケースに合格できません。

出力には、共通のサブシーケンスの長さが含まれている必要があります。例えば、入力のための共通部分はこれらの3つのリストの（1,3）であるため

3 
1 2 3 
3 
2 1 3 
3 
1 3 5 

出力あります。

失敗したケースの実行時間は0.04秒で、自分のテストの大部分がはるかに高速に機能していたため、リストがかなり長いように見えます。

ありがとうございました！

更新2：私は別のバージョンを試しました。最初に、2つのリストの中で最も長い共通サブシーケンスを見つけて、結果と3番目のリストに再び使用します。

def lcs2(a, b): 
    start_b = 0 
    result = [] 
    for i in range(len(a)): 
     for j in range(start_b, len(b)): 
      if a[i] == b[j]: 
       start_b = j+1 
       result.append(a[i]) 
       break 
    return result 


def lcs2_reversed(a, b): 
    # check reversed sequence which can be with different order 
    a_rev = a[::-1] 
    b_rev = b[::-1] 
    result_reversed = lcs2(a_rev, b_rev)[::-1] 
    return result_reversed 

def lcs3_reversed(a, b, c): 
    lcs2_str = lcs2(a, b) 
    lcs2_rev = lcs2_reversed(a, b) 
    lcs3_str_str = lcs2(lcs2_str, c) 
    lcs3_rev_rev = lcs2_reversed(lcs2_rev, c) 
    lenghts = [len(lcs3_str_str), len(lcs3_rev_rev)] 
    return max(lenghts) 

if __name__ == '__main__': 
    an = input() 
    a = input().split() 
    bn = input() 
    b = input().split() 
    cn = input() 
    c = input().split() 
    print(max(lcs3_reversed(a, b, c), lcs3_reversed(a, c, b), lcs3_reversed(b, a, c), 
       lcs3_reversed(b, c, a), lcs3_reversed(c, a, b), lcs3_reversed(c, b, a))) 

さらに、私はすべての注文の組み合わせを試しましたが、役に立たなかった...この最後のテストケースに合格できません。

Answer 1

あなたの例のようなものを壊し：

a = [1,2,7,3,7] 
b = [2,1,2,3,7] 
c = [1,2,3,1,7] 

（私が正しく運動を理解している場合）のシーケンスは[1,2,3,7]する必要がありますが、問題はaの最後の要素はbの最後の要素にマッチしてしまうことですcであり、これは最後の要素にstart_bとstart_cが設定されていることを意味し、したがってループは終了しています。