Longest Common Subsequence

Q: En Uzun Ortak Alt Dizinin zaman karmaşıklığı nedir?

Tablo çözümü O(n × m) zamanda çalışır; her önek çifti için bir hücre hesaplanır. Tablonun tamamı için O(n × m) bellek gerekir; iki satır kullanıldığında ise O(min(n, m)) bellek yeterlidir. Tablo kullanmayan yalın özyineleme üstel zamana ihtiyaç duyar.

OrtaDinamik programlama

+10

İki dizge, text1 ve text2 veriliyor. Bir dizgenin alt dizisi, harflerinin bazılarını özgün sıralarında tutup geri kalanını çıkarır; tutulan harflerin yan yana olması gerekmez. Her iki dizgenin de alt dizisi olan en uzun dizgenin uzunluğunu, iki dizgenin ortak hiçbir harfi yoksa 0 değerini döndürün.

Fonksiyon

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: ilk dize
text2string: ikinci dize
Döndürürinteger: en uzun ortak alt dizinin uzunluğu

Kısıtlar

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Her iki dize de yalnızca küçük İngilizce harfler içerir.

Örnekler

Girdi: text1 = "stone"text2 = "longest"
Çıktı: 3
Açıklama: o, n ve e her iki kelimede de bu sırayla görünür, bu yüzden ortak olan one'dır, uzunluğu 3'tür. s ve t harfleri longest sözcüğünde en sonda, ancak stone sözcüğünde en başta yer alır; dolayısıyla bunları kullanmak en fazla st verir.

Girdi: text1 = "pear"text2 = "reap"
Çıktı: 2
Açıklama: ea her iki kelimede de bulunur. İki kelimede p ve r, ea dizisinin zıt taraflarında yer alır; bu yüzden hiçbiri ona katılamaz ve cevap 2'dir.

Ek soru

En uzun ortak alt dizilerden birini uzunluğuyla birlikte döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Açgözlü eşleştirme başarısız olur: cab içindeki c harfini abc içindeki son c ile eşleştirmek, a ve b için geriye hiçbir şey bırakmaz; bu eşleştirmeyi atlamak ise ab sonucunu bulur. İki önek için cevap, daha kısa öneklerin cevaplarına bağlıdır; bu nedenle her çifti bir kez çözmek için (n+1) × (m+1) boyutunda bir tablo kullanılır. Her satır yalnızca üstündeki satırı okuduğundan, iki satır yeterlidir.

İlk harfleri özyinelemeyle karşılaştır

Doğru, ama en büyük testlerde bitmiyor

Sezgi

lcs(i, j), text1[i:] ve text2[j:] sonekleri için yanıt olsun. İlk harfleri eşitse onları eşleştir: Bu çifti atlayan en uzun ortak alt dizi, ilk çiftini bununla değiştirerek kısalmadan devam edebilir. Bu nedenle yanıt 1 + lcs(i+1, j+1) olur.

Harfler farklıysa ikisi birden kullanılamaz; çünkü eşleri çiftlerin kesişmesine yol açar. Bu yüzden harflerden biri çıkarılabilir: max(lcs(i+1, j), lcs(i, j+1)). Boş bir sonek 0 verir.

Her uyuşmazlık iki çağrı başlatır. Ortak harfi olmayan iki 20 harfli dizge, şimdiden yaklaşık 2.8 × 10^11 çağrı gerektirir; oysa yalnızca (n+1) × (m+1) farklı (i, j) çifti vardır. Dolayısıyla çağrıların neredeyse tamamı daha önce yapılan bir çağrıyı tekrarlar.

Algoritma

i ve j konumlarından başlayan sonekler için lcs(i, j) yazın.
i veya j kendi dizgesinin sonunu geçmişse 0 döndürün.
text1[i] == text2[j] ise 1 + lcs(i+1, j+1) döndürün.
Aksi takdirde max(lcs(i+1, j), lcs(i, j+1)) döndürün.
Cevap lcs(0, 0) olur.

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Bir önekler tablosu doldurun

Sezgi

dp[i][j], text1 dizgesinin ilk i harfi ve text2 dizgesinin ilk j harfi için yanıt olsun; böylece 0 indeksi boş bir önek anlamına gelir ve 0. satır ile 0. sütun 0'dır. İki önekin son harflerini, text1[i-1] ve text2[j-1], karşılaştır: harfler eşitse eşleşir ve sonuç dp[i-1][j-1] + 1 olur; farklıysa harflerden biri atılır ve sonuç max(dp[i-1][j], dp[i][j-1]) olur. Bu, sondan okunan özyinelemedir.

Her hücre yukarıdaki, solundaki ve çapraz olarak yukarı-solundaki hücreleri okur; bu yüzden satır satır, soldan sağa doldurmak, bu hücrelerin her zaman hazır olmasını sağlar. pear ve reap için pea satırı [0, 0, 1, 2, 2] olur; rea için hücre 2'dir çünkü a, a ile eşleşir ve pe ile re için olan hücreye bir eklenir.

1000 harfli iki dizge yaklaşık 10^6 sabit zamanlı adım gerektirir.

Algoritma

(n+1) × (m+1) sıfırdan oluşan bir dp tablosu oluşturun.
1'den n'ye kadar i ve 1'den m'ye kadar j için text1[i-1] ile text2[j-1]'yi karşılaştırın.
Eşleşme varsa dp[i][j] = dp[i-1][j-1] + 1 olarak ayarlayın.
Aksi takdirde dp[i][j] = max(dp[i-1][j], dp[i][j-1]) olarak ayarlayın.
dp[n][m] değerini döndürün.

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Yalnızca iki satır tut

Sezgi

Bir satır tamamlandığında, üstündeki satırlar bir daha asla okunmaz. Tamamlanan satır için prev değerini, doldurulmakta olan satır için cur değerini tut ve her satırdan sonra bunları yer değiştir. Bağıntı ve sıra aynı kalır.

Yanıt, hangi dizgenin önce geldiğine bağlı değildir; bu yüzden satırları daha kısa olan boyunca ilerlet. Böylece her satır min(n, m) + 1 sayı içerir: en büyük girdiler için bir milyon hücre yerine 1001 hücre; adım sayısı yine 10^6.

Algoritma

text2, text1'den daha uzunsa onları yer değiştir.
prev ve cur oluştur; her biri m + 1 tane sıfır içersin. Burada m, daha kısa olan uzunluktur.
text1'in her harfi için, üstteki satırda prev'i okuyarak cur[1..m]'yi tablodaki kuralla doldur.
prev ve cur'un yerini değiştir.
prev[m]'i döndür.

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Tuzaklar ve uç durumlar

Tablo indekslerini dize indeksleriyle karıştırmak. dp[i][j] hücresi text1[i-1] ile text2[j-1] değerlerini karşılaştırır; çünkü 0. satır boş öneke karşılık gelir.
Eşleşme olduğunda dp[i-1][j-1] değerine 1 eklemek yerine max(dp[i-1][j], dp[i][j-1]) değerine 1 eklemek. Bu, aynı harfin iki kez kullanılmasına yol açabilir: aa ile a karşılaştırıldığında sonuç 1 yerine 2 olur.
Hâlâ okumakta olduğunuz satıra yazmak. İki satır kullanırken, yukarıdaki satırdaki her değer prev içinden alınmalı ve cur[0] değeri 0 kalmalıdır.
Python'da 1000 harflik dizelerde özyinelemeyi önbelleğe almak. Çağrı derinliği 2000'e ulaşır ve varsayılan 1000 sınırını aşar.

Sıkça sorulan sorular3

En Uzun Ortak Alt Dizinin zaman karmaşıklığı nedir?

Tablo çözümü O(n × m) zamanda çalışır; her önek çifti için bir hücre hesaplanır. Tablonun tamamı için O(n × m) bellek gerekir; iki satır kullanıldığında ise O(min(n, m)) bellek yeterlidir. Tablo kullanmayan yalın özyineleme üstel zamana ihtiyaç duyar.

En uzun ortak alt dizi ile en uzun ortak alt dizge arasındaki fark nedir?

Bir alt dizi, sıralama korunduğu sürece harfleri atlayabilir; bir alt dize ise yan yana duran harflerden oluşan bir bloktur. stone ve longest için en uzun ortak alt dizi one (3), en uzun ortak alt dize ise on (2) olur. Alt dize tablosu, uyuşmazlık durumunda komşu hücreyi kopyalamak yerine hücreyi 0'a sıfırlar.

LCS, diff araçları ve düzenleme mesafesiyle nasıl ilişkilidir?

Bir dosyanın iki sürümü arasındaki fark, satırlarının en uzun ortak alt dizisini korur ve diğer tüm satırları eklenmiş veya silinmiş olarak gösterir. Bir dizgeyi diğerine dönüştürmek için gereken en az ekleme ve silme sayısı n + m - 2 × LCS değeridir. Düzenleme mesafesi bir harfi değiştirmeye de izin verir, bu yüzden kendine ait bir tabloya ihtiyaç duyar.

def longestCommonSubsequence(text1, text2):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

text1 = "stone"
text2 = "longest"

Beklenen Çıktı

Longest Common Subsequence

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

İlk harfleri özyinelemeyle karşılaştır

Bir önekler tablosu doldurun

Yalnızca iki satır tut

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler