LCS tanımı
- Algoritmalar kursu
- İleri seviye
- Ders 9/56
- 4 dk
İ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.
Başlangıç kodu
def lcs_brute(s1, s2):
# LCS brute-forceÖrnek çözüm
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"))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 LCS hangi tanımı kullanır?
- Önek
- Alt dize
- Alt dizi Doğru cevap
- Sonek
Açıklama: Alt dizi.
2 LCS kısaltması
LCS: Longest Common ____LCS: Longest Common SubsequenceAçıklama: Subsequence doğru.
3 LCS tanımı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
LCS |
Ortak alt dizi |
subsequence |
Sıralı |
substring |
Ardışık |
DP |
Dinamik |