Z-funksiyasi
Eslatma. Ushbu maqolada ga asoslangan indekslar ishlatiladi, ya’ni satrining birinchi belgisi indeksga, oxirgisi esa — ga ega.
satrining pozitsiyasidagi Z-funksiya — bu pozitsiyadan boshlanadigan ostsatrning butun satri prefiksi bilan mos keladigan eng katta prefiksining uzunligi.
Formal ravishda:
qiymati odatda kelishuvga ko‘ra yoki ga teng deb olinadi.
murakkablikka ega oddiy realizatsiya mavjud, bu yerda — satr uzunligi.
Har bir pozitsiya uchun belgilar mos kelguncha ni oshiramiz.
satrining pozitsiyadan boshlanib, uzunligi bo‘lgan, ya’ni satr prefiksi bilan mos keladigan ostsatrini Z-blok deb ataymiz.
Algoritm uchun ikkita o‘zgaruvchi kiritamiz:
Dastlab:
qiymatlari pozitsiyalar uchun allaqachon ma’lum deb faraz qilamiz.
ni topamiz.
Pozitsiya joriy Z-blokdan tashqarida.
Belgilarni bevosita solishtiramiz:
ular mos kelguncha.
Birinchi mos kelmaydigan indeks — bo‘lsin. Unda:
Chegaralarni yangilaymiz:
Pozitsiya joriy Z-blok ichida.
Simmetrik pozitsiyani ko‘rib chiqamiz:
Shunda ma’lum:
Kengaytirishdan so‘ng yangilaymiz:
Chiziqli realizatsiya :
Satrlar berilgan:
ning dagi barcha uchrashuvlarini topish talab qilinadi.
Satrni tuzamiz:
bu yerda belgisi — va da uchramaydigan ajratuvchi.
satrining Z-funksiyasini hisoblaymiz.
Matn dagi har bir pozitsiya uchun:
Agar:
bo‘lsa, satrining pozitsiyasida ning uchrashuvi boshlanadi.
Aks holda — yo‘q.
Asimptotika:
Uzunligi bo‘lgan satri berilgan.
Shunday eng qisqa satrini topingki:
( ning bir yoki bir nechta nusxasi).
satrining Z-funksiyasini hisoblaymiz va sonining barcha bo‘luvchilari ni ko‘rib chiqamiz.
Agar quyidagisi bajarilsa:
unda satrning periodi ga teng, va uni uzunlikkacha siqish mumkin.
Shunday larning eng kichigini olamiz.
Asimptotika:
vector<int> z_function_slow(const string& s) {
int n = s.size();
vector<int> z(n);
for (int i = 1; i < n; i++) {
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
}
return z;
}
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(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];
}
}
return z;
}