Переберем все индексы i от 1 до N и для каждого i будем искать значение зеркальной z-функции.
Для вычисления значения зеркальной z-функции понадобится еще одна функция – z-функция. Зеркальная z-функция в индексе i равна максимальному значению k, такому что z-функция в индексе i – k равна z-функции в индексе i.
Чтобы вычислить значения зеркальной z-функции для всех индексов i от 1 до N, применим следующий алгоритм:
1. Инициализируем массив зеркальной z-функции z с длиной N и заполняем его нулями.
2. Переберем все индексы i от 1 до N.
3. Вычислим зеркальную z-функцию z[i] следующим образом:
3.1. Инициализируем переменные left и right с значениями i и i.
3.2. Пока right < N и S[left] равно S[right]:
3.2.1. Увеличиваем значения left и right на 1.
3.3. Записываем в z[i] значение right - i.
4. Выводим значения массива z.
Алгоритм работает за O(N), где N - длина строки S. Так как зеркальная z-функция рассчитывается для всех индексов i от 1 до N, общее время работы алгоритма будет пропорционально N.
Реализация алгоритма на Python может выглядеть так:
```python
def mirror_z_function(S):
N = len(S)
z = [0] * N
for i in range(1, N):
left, right = i, i
while right < N and S[left] == S[right]:
left += 1
right += 1
z[i] = right - i
return z
N = int(input())
S = input()
z_values = mirror_z_function(S)
for z in z_values:
print(z, end=' ')
```
Пример работы алгоритма:
Входные данные:
7
abcddcb
Выходные данные:
0 0 0 2 0 0 0