e-olymp 1309. Блоки строки

Условие задачи

Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.

Вычислить длины блоков строки S для всех позиций.

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

Единственная строка S (|S| ≤ 106).

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

В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.

Тесты:

Код программы:

 

 

 

Алгоритм

В данной задаче из-за того, что наша строка может принимать длину до  106 включительно, то необходим эффективный алгоритм. Я воспользовался алгоритмом вычисления Z-функции. Для начала мы заводим переменные left и right, в которых мы будем хранить координаты самого длинного отрезка, который совпадает с началом нашей строки. В начале цикла проверяем находится ли ячейчка, для которой ищется результат в отрезке между left и right. После прохождения цикла while, мы обновляем границы подстроки.

 

Код на ideone.com

Принятая задача на e-olymp.

Павел Загинайло
Павел Загинайло

Latest posts by Павел Загинайло (see all)

6 thoughts on “e-olymp 1309. Блоки строки

  1. Странно, как на е-олимпе хоть что-то набрало решение, которое выводит пробел в конце строки и не выводит перевод строки после вывода. Попробуйте заменить последний пробел на перевод строки и заслать решение.

  2. 1. Сначала изменил вывод. Теперь выводит вместо пробела перевод на новую строку. Все еще 92%.
    2. Увеличил размер массива. Теперь 1000100. Все равно 92%. Потом даже изменил на 2000200, ничего не изменилось.
    Измененный код по той же ссылке можно посмотреть. Программа не проходит буквально 5 тестов из 62.

  3. Все, наконец-то исправил код и теперь все работает. Проблема была в том, что при вводе строки с пробелами, в строку s не записывается все, что находится после пробела, включая его. Пост обновил!

Добавить комментарий