Условие задачи
Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.
Вычислить длины блоков строки S для всех позиций.
Входные данные
Единственная строка S (|S| ≤ 106).
Выходные данные
В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.
Тесты:
|
||
|
||
|
||
|
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <cstring> using namespace std; int main(){ int zf[1000000]; char s[1000000]; scanf("%[^\n]%*c", s); int n = strlen(s); int right=0,left=0; for(int i=1; i < n; ++i){ if(i<=right){ zf[i]=min(right-i+1,zf[i-left]); } while(s[zf[i]]==s[zf[i]+i]){ zf[i]++; } if(i+zf[i]-1>right){ left=i; right=i+zf[i]-1; } } for(int i=0; i < n; ++i){ cout << zf[i] << " "; } return 0; } |
Алгоритм
В данной задаче из-за того, что наша строка может принимать длину до 106 включительно, то необходим эффективный алгоритм. Я воспользовался алгоритмом вычисления Z-функции. Для начала мы заводим переменные left и right, в которых мы будем хранить координаты самого длинного отрезка, который совпадает с началом нашей строки. В начале цикла проверяем находится ли ячейчка, для которой ищется результат в отрезке между left и right. После прохождения цикла while, мы обновляем границы подстроки.
Странно, как на е-олимпе хоть что-то набрало решение, которое выводит пробел в конце строки и не выводит перевод строки после вывода. Попробуйте заменить последний пробел на перевод строки и заслать решение.
Этот баг на e-olymp поправили при переходе на новый движок.
И еще. Попробуйте сделать массивы на пару символов длиннее. Потому что строку длины 1е6 вы не прочтете.
1. Сначала изменил вывод. Теперь выводит вместо пробела перевод на новую строку. Все еще 92%.
2. Увеличил размер массива. Теперь 1000100. Все равно 92%. Потом даже изменил на 2000200, ничего не изменилось.
Измененный код по той же ссылке можно посмотреть. Программа не проходит буквально 5 тестов из 62.
Все, наконец-то исправил код и теперь все работает. Проблема была в том, что при вводе строки с пробелами, в строку s не записывается все, что находится после пробела, включая его. Пост обновил!
Странно, куда-то подевался мой комментарий. Но теперь уже неважно.
Кстати, судя по статистике Ваше решение по скорости приближается к моему, но тратит много больше памяти.
P.S. Конечно зачтено.