Longest Common Subsequence

Q: En Uzun Ortak Alt Dizi'nin zaman karmaşıklığı nedir?

Tablo çözümü O(n × m) zamanda çalışır; burada n ve m iki dizenin uzunluklarıdır: her önek çifti için bir hücre doldurur. Tablonun tamamı için O(n × m) bellek, iki satır kullanıldığında ise O(min(n, m)) bellek gerekir. Tablo kullanmayan yalın özyineleme üstel zamandadır.

Q: En uzun ortak alt dizinin kendisini nasıl yazdırırsınız?

Tablonun tamamını doldurun, ardından dp[n][m] konumundan geriye doğru ilerleyin. Geçerli hücredeki iki harf eşleşiyorsa, bu harf yanıtın bir parçasıdır: onu kaydedin ve çapraz olarak yukarı ve sola ilerleyin. Aksi takdirde, daha büyük değeri taşıyan üstteki veya soldaki komşu hücreye ilerleyin. Sonunda kaydedilen harfleri ters çevirin. İki satırlı sürüm bunu yapamaz, çünkü önceki satırları silip atmıştır.

OrtaDinamik programlama

+10

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

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, e her iki sözcükte de bu sırayla görünür, bu nedenle one uzunluğu 3 olan ortak bir alt dizidir. longest sözcüğünde s ve t harfleri sonda gelirken, stone sözcüğünde başta gelir; bu yüzden bunları kullanan ortak bir alt dizi yalnızca st olabilir ve bu daha kısadır.

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

Gönderirken +19 gizli test

Ek soru

En uzun ortak alt dizinin uzunluğunu değil, kendisini 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

Harfleri açgözlü bir şekilde eşleştirmek işe yaramaz. Bir harf, diğer dizgede birçok yerde eşleşebilir ve ilk eşleşme daha iyi eşleşmeleri engelleyebilir: cab içindeki c harfini abc dizgesinin sonundaki c ile eşleştirmek, a ve b için eşleşme bırakmaz; oysa bu harfi atlamak ab sonucunu bulur. Bu sorunu çözen fikir, iki önek için cevabın yalnızca biraz daha kısa öneklerin cevaplarına bağlı olmasıdır. (n+1) × (m+1) sayıdan oluşan bir tablo, her çifti bir kez çözer ve 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:] son ekleri için yanıt olsun. İlk harflerine bakın. Eşitlerse onları eşleştirin: bu eşleşmeyi kullanmayan en uzun ortak alt dizi, ilk eşleşmesini bununla değiştirerek kısalmadan devam edebilir. Dolayısıyla yanıt 1 + lcs(i+1, j+1) olur.

Harfler farklıysa ikisi birden kullanılamaz; çünkü her biri yalnızca diğer dizenin daha sonraki bir harfiyle eşleşebilir ve eşleşmeler kesişir. Bu nedenle biri çıkarılabilir: yanıt max(lcs(i+1, j), lcs(i, j+1)) olur. Son eklerden biri boş olduğunda ortak hiçbir şey yoktur ve yanıt 0'dır.

Yavaştır, çünkü her uyuşmazlık iki çağrı başlatır. Dizeler hiçbir harfi paylaşmıyorsa, bir dize tükenene kadar her çağrıda uyuşmazlık olur ve çağrı sayısı iki dizenin iç içe geçirilme yollarının sayısı gibi büyür. 20 harfli iki dize için bu yaklaşık 2.8 × 10^11 çağrıdır; büyük testlerde her biri 1000 harf uzunluğundadır. Oysa yalnızca (n+1) × (m+1) farklı (i, j) çifti vardır, dolayısıyla neredeyse her çağrı daha önce yapılmış birini tekrarlar.

Algoritma

i ve j konumlarından başlayan son ekler 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 hâlde max(lcs(i+1, j), lcs(i, j+1)) döndürün.
Yanıt lcs(0, 0) değeridir.

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)

Önekler tablosunu doldurun

Sezgi

Durum. dp[i][j], text1 dizgesinin ilk i harfi ile text2 dizgesinin ilk j harfinin en uzun ortak alt dizisi olsun. Öneklerle çalışmak, 0 indeksinin boş dizgeyi ifade etmesini sağlar.

Bağıntı. İki önekin son harflerini, text1[i-1] ve text2[j-1] değerlerini karşılaştır. Eşitlerse onları eşleştir: dp[i][j] = dp[i-1][j-1] + 1. Eşit değillerse birini çıkar: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Bu, sondan okunarak yapılan özyinelemeyle aynı mantıktır. Temel durum: 0. satır ve 0. sütun 0'dır; çünkü boş bir önekin hiçbir şeyle ortak harfi yoktur. Sıra: Her hücre üstündeki, solundaki ve çapraz olarak sol üstündeki hücreyi okur; bu nedenle satır satır, soldan sağa doldurmak, bu hücrelerin her zaman hazır olmasını sağlar. Yanıt dp[n][m] değeridir.

pear ve reap için pea satırı [0, 0, 1, 2, 2] olur. rea için olan hücresi 2'dir; çünkü a, a ile eşleşir ve bu nedenle pe ile re için olan 1 değerli hücreye bir eklenir. Son hücre, pear ile reap karşılaştırması, birbirinden farklı olan r ve p harflerini karşılaştırır ve iki komşusundan büyük olanı, yani 2'yi alır.

Tabloda (n+1) × (m+1) hücre bulunur ve her biri sabit miktarda işlem gerektirir: 1000 harfli iki dizge için yaklaşık 10^6 adım. Özyinelemenin belleğe alınmış sürümü aynı hücreleri doldurur, ancak n + m çağrı derinliğine kadar özyinelemeli çalışır; bu da Python gibi dillerde varsayılan çağrı yığını boyutunu aşar.

Algoritma

(n+1) × (m+1) sıfırdan oluşan bir dp tablosu oluşturun.
i için 1'den n'ye ve j için 1'den m'ye kadar, 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 bırakın

Sezgi

Tablonun i. satırı yalnızca i-1. satırı ve kendi önceki hücrelerini okur. Bir satır tamamlandıktan sonra üstündeki satırlar bir daha okunmaz. Bu yüzden tamamlanmış satır için prev, doldurulmakta olan satır için cur olmak üzere iki dizi tutun ve her satırdan sonra bunları yer değiştirin. Bağıntı ve sıralama tamamen aynı kalır.

İki dizenin ortak alt dizisi, hangi dizenin önce olduğuyla ilgilenmez; bu yüzden dizelerin yerini değiştirip satırların daha kısa olan dizi boyunca ilerlemesini sağlayabilirsiniz. Böylece her satırda min(n, m) + 1 sayı bulunur: en büyük girdiler için bir milyon hücre yerine 1001 hücre; yapılan iş yine 10^6 adımdır.

Her satırın ilk girdisi, kısa dizenin boş bir önekini temsil eder; bu yüzden 0 olarak kalmalıdır. Yanıt, tamamlanmış son satırın son girdisidir.

Algoritma

text2, text1'den daha uzunsa, onları yer değiştir.
Her biri m + 1 sıfır içeren prev ve cur oluştur; burada m daha kısa olanın uzunluğudur.
text1'in her harfi için, yukarıdaki satır için prev'i okuyarak cur[1..m]'i 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

Özyineleme bağıntısı kısadır ve hataların çoğu bir fazla ya da bir eksik saymaktan veya eşleşmeyi yanlış yere eklemekten kaynaklanır.

Tablo indekslerini dizge 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 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.
İki işaretçiyle açgözlü eşleştirme yapmak. cab ile abc karşılaştırıldığında iki c harfi eşleştirilir ve sonuç 1 olurken, ab 2 verir.
Hâlâ okuduğun satıra yazmak. İki satır kullanırken, yukarıdaki satırdaki her değer prev üzerinden alınmalı ve cur[0] 0 kalmalıdır.
Yanlışlıkla en uzun ortak alt dizgeyi çözmek. Bir alt dizi harfleri atlayabilir; alt dizge atlayamaz.
1000 harfli dizgelerde özyineleme kullanarak önbelleğe alma yapmak. Çağrı derinliği 2000'e ulaşır; bu, Python'ın varsayılan 1000 sınırını aşar.

Sıkça sorulan sorular4

En Uzun Ortak Alt Dizi'nin zaman karmaşıklığı nedir?

Tablo çözümü O(n × m) zamanda çalışır; burada n ve m iki dizenin uzunluklarıdır: her önek çifti için bir hücre doldurur. Tablonun tamamı için O(n × m) bellek, iki satır kullanıldığında ise O(min(n, m)) bellek gerekir. Tablo kullanmayan yalın özyineleme üstel zamandadır.

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

Bir alt dizi, sıra korunduğu sürece harfleri atlayabilir; alt dize ise yan yana gelen 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 sürümünde benzer bir tablo kullanılır, ancak eşleşme olmadığında hücre komşusundaki değeri kopyalamak yerine 0'a sıfırlanır.

En uzun ortak alt dizinin kendisini nasıl yazdırırsınız?

Tablonun tamamını doldurun, ardından dp[n][m] konumundan geriye doğru ilerleyin. Geçerli hücredeki iki harf eşleşiyorsa, bu harf yanıtın bir parçasıdır: onu kaydedin ve çapraz olarak yukarı ve sola ilerleyin. Aksi takdirde, daha büyük değeri taşıyan üstteki veya soldaki komşu hücreye ilerleyin. Sonunda kaydedilen harfleri ters çevirin. İki satırlı sürüm bunu yapamaz, çünkü önceki satırları silip atmıştır.

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 bulur; bu dizinin dışındaki her satır eklenmiş veya silinmiş olarak gösterilir. Aynı şekilde, bir dizgeyi diğerine dönüştürmek için gereken en az ekleme ve silme sayısı n + m - 2 × LCS olur. Düzenleme uzaklığı, bir harfi değiştirmeye de izin verir; bu nedenle her hücre için üçüncü bir seçenek içeren kendi tablosunu kullanır.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

text1 = "stone"
text2 = "longest"

Beklenen

Longest Common Subsequence

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

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

Önekler tablosunu doldurun

Yalnızca iki satır bırakın

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler