# Кластеризация данных

**Автор:**
Непесов Рустам

**Тема:**
Машинное обучение и анализ данных

---

## Теоретическая база

Z-функция строки s определяется как массив z, где z[i] равно длине максимальной подстроки, начинающейся с i-той позиции, которая равна префиксу s.
Пример: Для строки abacabadaba префикс-функция будет выглядеть как:
	0 0 1 0 3 0 1 0 3 0 1
Z-функция этой строки будет:
	0 0 1 0 3 0 1 0 3 0 1

### Алгоритм
Инициализация: Создаем массив z такой же длины, как и пассив n.
Установим z[0] = 0, так как Z-функция для первого символа всегда равна 0.
Цикл по индексам: Проходим по всем индексам от 1 до n – 1:
Если n[i]> 0, устанавливаем начальное значение z[i] = z[n[i-1]].
Это значение указывает, насколько мы можем «перенести» информацию о совпадении префикса.
Если z[i] не может быть больше n – i(то есть не выходит за границы строки), увеличиваем z[i], пока символы совпадают.
Обновление границ: Если I + z[i] – 1 становится больше текущей правой границы r, обновляем границы Z-блока.

**Ограничения метода:**
- Ограничение по длине строки.
- Зависимость от корректности массива префикс-функции.
- Применение в специфических задачах.
- Обработка спец.символов

### Примеры применения
- Поиск подстрок.
- Сравнение строк.
- Алгоритм Кнута-Морриса-Пратта.

---

## Условие
Дан массив префикс-функции. Исходная строка не дана. Вычислите за O(n) зет-функцию этой строки.

### Входные данные
- Первое число: n (1 ≤ n ≤ 100000) — длина массива префикс-функции.
- Следующие n чисел: значения префикс-функции ni (0 <= ni < n) – массив префикс-функции, где каждый элемент представляет длину максимального префикса, совпадающего с суффиксом строки, заканчивающимся в позиции i.

### Выходные данные
- n строк, описывающих значения Z-функции zi (0 <= zi <= n) – массив Z-функции для строки, соответствующий данному массиву префикс-функции.

---

## Пример
**Ввод:**

```
11
0 0 1 0 2 1 0 3 0 4 1
```

**Вывод:**

```
0 0 1 0 2 1 0 3 0 4 1
```
**Ввод:**

```
10
0 0 1 0 2 1 0 3 0 4
```

**Вывод:**

```
0 0 1 0 2 1 0 3 0 4
```

#En:
# Data clustering

**Author:**
Nepesov Rustam

**Topic:**
Machine learning and data analysis

---

## Theoretical basis

The Z-function of a string s is defined as an array z, where z[i] is equal to the length of the maximum substring starting from the i-th position, which is equal to the prefix of s.

Example: For the string abacabadaba, the prefix function will look like:
0 0 1 0 3 0 1 0 3 0 1
The Z-function of this string will be:
0 0 1 0 3 0 1 0 3 0 1

### Algorithm
Initialization: Create an array z of the same length as the passive n.
Set z[0] = 0, since the Z-function for the first character is always 0.
Loop through indices: Loop through all indices from 1 to n – 1:
If n[i]> 0, set the initial value z[i] = z[n[i-1]].
This value indicates how much we can “carry over” the information about the prefix match.
If z[i] cannot be greater than n – i (i.e. does not go beyond the string boundaries), increment z[i] while the characters match.
Updating the boundaries: If I + z[i] – 1 becomes greater than the current right boundary r, update the boundaries of the Z-block.

**Method limitations:**
- Limitation on the string length.
- Dependence on the correctness of the prefix function array.
- Application in specific tasks.
- Processing special characters

### Application examples
- Search for substrings.
- Comparison of strings.
- Knuth-Morris-Pratt algorithm.

---

## Condition
Given a prefix function array. No original string. Calculate the Z-function of this string in O(n).

### Input
- First number: n (1 ≤ n ≤ 100000) — length of the prefix function array.
- Next n numbers: prefix function values ni (0 <= ni < n) — prefix function array, where each element represents the length of the maximum prefix that matches the suffix of the string ending at position i.

### Output
- n strings describing Z-function values zi (0 <= zi <= n) — Z-function array for the string corresponding to the given prefix function array.

---

## Example
**Input:**

```
11
0 0 1 0 2 1 0 3 0 4 1
```

**Output:**

```
0 0 1 0 2 1 0 3 0 4 1
```
**Input:**

```
10
0 0 1 0 2 1 0 3 0 4
```

**Output:**

```
0 0 1 0 2 1 0 3 0 4