Algoritmalar
tr

Z-Algoritması

Dizeler O(n) O(n)

Her konum için, oradan başlayıp dizenin önekiyle eşleşen en uzun alt dizenin uzunluğunu hesaplar — bir [l, r) penceresini yeniden kullanarak.

text
A100
A·1
B·2
X·3
A·4
A·5
Y·6
A·7
A·8
B·9
i=0l=0r=0
1/24

Tanım gereği z[0] = n.

Değişmezz[i], i'de başlayıp metnin bir önekiyle eşleşen en uzun parçanın uzunluğudur.

z-algorithm.c
void zArray(const char *s, int n, int z[]) {
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r)
            z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n &&
               s[z[i]] == s[i + z[i]])
            z[i]++;
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
}

Z-Algoritması nasıl çalışır?

Z[i] = i'den başlayıp dizenin kendi önekiyle eşleşen en uzun alt dizenin uzunluğu. Korunan [l, r) eşleşme penceresi, her Z değerinin sıfırdan değil aynadaki eski değerden başlamasını sağlar.

Ne zaman kullanılır?

Desen eşleme (P#T ara), dize periyodikliği, önek tabanlı benzerlik.