Z-algoritması
- Algoritmalar kursu
- Uzman seviye
- Ders 16/41
- 4 dk
Z-fonksiyonuyla eşleşme indekslerini öğrenirsin.
Z-algoritması
Z-algoritması, bir dizenin her konumu için Z-dizisi'ni hesaplar. Z[i], dizenin başlangıcıyla i. konumdan başlayan alt dizenin en uzun ortak önekinin uzunluğudur.
Örneğin "aabxaab" için Z = [0, 1, 0, 0, 3, 1, 0]'dır. Z-değerleri, örüntü eşlemede, tekrar bulmada ve sıkıştırma uygulamalarında kullanılır.
Algoritma doğrusal zamanda, yani O(n)'de çalışır; iki gösterge ile [L, R] penceresini korur.
Z penceresi
Z-algoritması [L, R] penceresini korur; bu pencere, R en uzak konuma ulaşmış eşleşmedir. Yeni i için i R'den büyükse, naif karşılaştırma yaparız.
i R'den küçük veya eşitse, Z[i] en az min(Z[i-L], R-i+1) olur. Bu sayede önceki Z-değerlerini yeniden kullanırız.
Pencere her uzadığında R güncellenir; toplam çalışma O(n)'dir.
Uygulama z_function fonksiyonu
z_function(s) yaz. Dizinin Z-dizisini döndür. print(z_function("aabxaab")) ile [0, 1, 0, 0, 3, 1, 0] yazdır.
Başlangıç kodu
def z_function(s):
# Z-dizisini hesaplaÖrnek çözüm
def z_function(s):
# Z-dizisini hesapla
n = len(s)
z = [0] * n
L = R = 0
for i in range(1, n):
if i <= R:
z[i] = min(R - i + 1, z[i - L])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > R:
L = i
R = i + z[i] - 1
return z
print(z_function("aabxaab"))Beklenen çıktı
[0, 1, 0, 0, 3, 1, 0]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Z[i] neyi temsil eder?
s = "aabxaab"- Başlangıç ve i. sonek arasındaki en uzun ortak önek Doğru cevap
- Dizenin uzunluğu
- i. karakterin ASCII değeri
- i'den sonraki eşleşme sayısı
Açıklama: Z[i], başlangıç ve i. sonek arasındaki en uzun ortak önektir.
2 Z-dizi başlangıcı
z = [0] * n
____ = 0
L = R = 0z = [0] * n
z[0] = 0
L = R = 0Açıklama: z[0] genelde 0 kabul edilir.
3 Z kavramları
| Kavram | Anlamı |
|---|---|
Z[i] |
Ortak önek uzunluğu |
[L, R] |
Pencere |
O(n) |
Doğrusal zaman |
z[0] |
Sıfır kabul edilir |