Z-функсия
Эзоҳ. Дар ин мақола индексгузории бар асоси истифода мешавад, яъне аломати якуми сатри индекси дорад, ва охирин — .
Z-функсия-и сатри дар мавқеи — ин дарозии бузургтарин префикси зерсатре мебошад, ки аз мавқеи оғоз мешавад ва бо префикси тамоми сатри мувофиқат мекунад.
Расман:
Қимати одатан мувофиқи созиш баробари ё қабул карда мешавад.
Як татбиқи содда бо мураккабии вуҷуд дорад, ки дар он — дарозии сатр аст.
Барои ҳар мавқеи мо -ро зиёд мекунем, то даме ки аломатҳо мувофиқат кунанд.
Мо Z-блок меномем зерсатри сатри -ро, ки аз мавқеи оғоз мешавад ва дарозии дорад, яъне бо префикси сатр мувофиқат мекунад.
Барои алгоритм ду тағйирёбандаро ворид мекунем:
Дар оғоз:
Фарз мекунем, ки қиматҳои аллакай барои мавқеъҳои маълуманд.
-ро меёбем.
Мавқеъ берун аз Z-блоки ҷорӣ.
Аломатҳоро мустақиман муқоиса мекунем:
то даме ки онҳо мувофиқат кунанд.
Бигузор индекси аввалини номувофиқ — бошад. Он гоҳ:
Сарҳадҳоро нав мекунем:
Мавқеъ дар дохили Z-блоки ҷорӣ.
Мавқеи симметриро баррасӣ мекунем:
Он гоҳ маълум аст:
Пас аз васеъкунӣ нав мекунем:
Татбиқи хаттӣ :
Сатрҳо дода шудаанд:
Лозим аст ҳамаи даромадҳои -ро дар ёфтан.
Сатр месозем:
ки дар он аломати — ҷудокунандаест, ки дар ва во намехӯрад.
Z-функсияи сатри -ро ҳисоб мекунем.
Барои ҳар мавқеи дар матни :
Агар:
пас дар мавқеи -и сатри даромади оғоз мешавад.
Дар акси ҳол — не.
Асимптотика:
Сатри бо дарозии дода шудааст.
Кӯтоҳтарин сатри -ро ёбед, чунин ки:
(як ё чанд нусхаи ).
Z-функсияи сатри -ро ҳисоб мекунем ва ҳамаи тақсимкунандаҳои -и адади -ро мегардем.
Агар иҷро шавад:
пас сатр давраи дорад, ва онро то дарозии фишурда кардан мумкин аст.
Ҳамин -и минималиро мегирем.
Асимптотика:
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;
}