LCS tanımı

İki dizinin en uzun ortak alt dizisini öğrenirsin.

LCS tanımı

En uzun ortak alt dizi (LCS), iki dizinin ortak en uzun alt dizisidir. Sıra korunur, ardışıklık gerekmez.

Örnek: "ABCBDAB" ve "BDCAB" için LCS "BCAB" uzunluğu 4'tür.

LCS; DNA hizalama, diff araçları ve yazım denetiminde kullanılır; önemli bir DP problemidir.

Alt dizi vs alt dize

Alt dizi (subsequence) sırayı korur ama ardışık olmak zorunda değildir. Alt dize (substring) ardışık olmak zorundadır.

LCS, alt dizi tanımını kullanır; bu yüzden daha esnektir.

Bu ayrım, LCS ile en uzun ortak alt dize arasındaki temel farktır.

Uygulama LCS uzunluk deneme

lcs_brute(s1, s2) yaz. İki dizinin LCS uzunluğunu brute-force ile bul. print(lcs_brute("ABC", "AC")) ile 2 yazdır.

Örnek çözümü göster

def lcs_brute(s1, s2):
    # LCS brute-force
    if not s1 or not s2:
        return 0
    if s1[0] == s2[0]:
        return 1 + lcs_brute(s1[1:], s2[1:])
    return max(lcs_brute(s1[1:], s2), lcs_brute(s1, s2[1:]))
print(lcs_brute("ABC", "AC"))

Kendini test et

LCS hangi tanımı kullanır?
- Önek
- Alt dize
- Alt dizi
- Sonek
Cevabı göster

Alt dizi — Alt dizi.

LCS kısaltması

LCS: Longest Common ____

Cevabı göster

LCS: Longest Common Subsequence

LCS tanımı: kavramları eşleştir

LCS

Ortak alt dizi
subsequence

Sıralı
substring

Ardışık
DP

Dinamik

Sıradaki ders: DP tablosu

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler