Z-algoritması

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.

Örnek çözümü göster

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"))

Kendini test et

Z[i] neyi temsil eder?
```
s = "aabxaab"
```
- Başlangıç ve i. sonek arasındaki en uzun ortak önek
- Dizenin uzunluğu
- i. karakterin ASCII değeri
- i'den sonraki eşleşme sayısı
Cevabı göster

Başlangıç ve i. sonek arasındaki en uzun ortak önek — Z[i], başlangıç ve i. sonek arasındaki en uzun ortak önektir.

Z-dizi başlangıcı

z = [0] * n
____ = 0
L = R = 0

Cevabı göster

z = [0] * n
z[0] = 0
L = R = 0

Z kavramları

Z[i]

Ortak önek uzunluğu
[L, R]

Pencere
O(n)

Doğrusal zaman
z[0]

Sıfır kabul edilir

Sıradaki ders: Suffix array

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler