Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Z-функция

(Время: 2 сек. Память: 16 Мб Сложность: 54%)

Дана непустая строка S длиной N символов. Будем считать, что элементы строки нумеруются от 1 до N.

Для каждой i-й позиции строки S определим Z-блок как наибольшую подстроку, которая начинается в этой позиции и совпадает с некоторым началом всей строки S. Значением Z-функции Z(i) будем считать длину этого Z-блока. При i=1 будем считать, что Z(1)=0, несмотря на то, что в начале строки строка совпадает сама с собой.

Требуется для всех i от 1 до N вычислить значение Z(i).

Входные данные

В единственной строке входного файла INPUT.TXT записана строка, состоящая из символов с кодами ASCII от 33 до 127. Длина строки не превышает 106.

Выходные данные

В выходной файл OUTPUT.TXT выведите все значения Z-функции.

Примеры

INPUT.TXTOUTPUT.TXT
1ABRACADABRA0 0 0 1 0 1 0 4 0 0 1
2ABACABADABACABA0 0 1 0 3 0 1 0 7 0 1 0 3 0 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Простые задачи
 Алгоритмы на строках
 Полиномиальный хеш
 A. Антипалиндром
 B. Префикс-функция
 C. Z-функция
 D. Поле чудес
 E. Поиск подстроки
 F. Сдвиг текста
 G. Циклическая строка
 H. Суффиксы
 I. Количество различных подстрок
 J. Дендрохронология
 K. Abracadabra
 L. Алгоритм Манакера

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru