En Uzun Ortak Altdizi

Question

Ben üç Dizilerin uzun ortak sonradan gelme benim sürümünü uyguladıktan, bir hata bulamıyorum. Ama Coursera sınıfçısı, son test vakasında başarısız olduğumu söylüyor. Bu algoritma neredeyse düzeltir ama bir belirli durumda yanlış cevap verir demektir. Ama hangi dava?

Kısıtlamalar: listenin uzunluğu bir kereden az değil ve 100'den büyük değil. Listelerdeki sayılar -10^9 ila 10^9 arasında tamsayılardır.

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)) 

Güncelleme:sizin tarafınızdan tanımlanan durumlarda çözmek için lcs3_reversed fonksiyonu eklendi. Herzaman test vakasını geçemez.

Çıkış ortak alt dizisinin uzunluğu içermelidir. Örneğin, giriş için: ortak bölüm bu 3 listeler için (1: 3) olduğu için

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

çıkış olup. Başarısız durum için

Süre 0,04 saniyedir ve listelediği oldukça uzun kendi testlerin çoğu çok daha hızlı çalıştı beri olduğu gibi görünüyor.

Yardımlarınız için teşekkürler!

Update2: Ben başka bir sürümünü denedim. Önce 2 listenin en uzun ortak alt dizisini buluruz ve daha sonra sonuçta ve 3-rd listesinde tekrar kullanırız.

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))) 

Ayrıca, tüm sipariş kombinasyonlarını denedim ama yardımcı olmadı ... Tekrar Bu son test durumunu geçemiyorum.

Answer 1

Sizin örnek gibi bir şeyle kırar: (Ben doğru egzersiz anlıyorum varsa) dizisi [1,2,3,7] olmalıdır

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

, ancak sorun a son elemanı b son elemanlarına eşleşti olur olduğunu ve c, yani start_b ve start_c öğelerinin son öğelere ayarlandığı ve bu nedenle döngülerin bittiği anlamına gelir.