Изменения
Новая страница: «==Определение== Z-функция от строки <tex>S</tex> и позиции <tex>x</tex>, это длина максимального префик…»
==Определение==
Z-функция от строки <tex>S</tex> и позиции <tex>x</tex>, это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>.
==Алгоритм поиска==
*'''Задача'''
Дана строка <tex>S</tex>. Необходимо построить массив <tex>Z</tex>, такой что <tex>Z[i]</tex> является префикс функцией данной строки с позиции <tex>i</tex>
*'''Описание алгоритма'''
*'''Код алгоритма'''
int[] z(String p) {
int[] ans = new int[p.length()];
ans[0] = 0;
int n = p.length();
int left = 0;
int right = 0;
for (int i = 1; i < n; i++) {
if (i > right) {
int j = 0;
while (i + j < n && p.charAt(i+j) == p.charAt(j)) {
j++;
}
ans[i] = j;
left = i;
right = i + j - 1;
} else {
if (ans[i - left] < right - i + 1) {
ans[i] = ans[i - left];
} else {
int j = 1;
while (j + right < n && p.charAt(j+right-i) == p.charAt(right + j)) {
j++;
}
ans[i] = right + j - i;
left = i;
right = right + j - 1;
}
}
}
return ans;
}</source>
Z-функция от строки <tex>S</tex> и позиции <tex>x</tex>, это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>.
==Алгоритм поиска==
*'''Задача'''
Дана строка <tex>S</tex>. Необходимо построить массив <tex>Z</tex>, такой что <tex>Z[i]</tex> является префикс функцией данной строки с позиции <tex>i</tex>
*'''Описание алгоритма'''
*'''Код алгоритма'''
int[] z(String p) {
int[] ans = new int[p.length()];
ans[0] = 0;
int n = p.length();
int left = 0;
int right = 0;
for (int i = 1; i < n; i++) {
if (i > right) {
int j = 0;
while (i + j < n && p.charAt(i+j) == p.charAt(j)) {
j++;
}
ans[i] = j;
left = i;
right = i + j - 1;
} else {
if (ans[i - left] < right - i + 1) {
ans[i] = ans[i - left];
} else {
int j = 1;
while (j + right < n && p.charAt(j+right-i) == p.charAt(right + j)) {
j++;
}
ans[i] = right + j - i;
left = i;
right = right + j - 1;
}
}
}
return ans;
}</source>
