Блог пользователя Truba

Задача из SPOJ (PLD)
Автор Truba, 12 лет назад, По-русски

Всем привет. Наткнулся на один пост в КФ и начал решать эту задачу про палиндромы. Написал Дерево Отрезков для нахождения Хеша от строки. Вроде бы все правильно но, WA на 9 тесте. Мой код лежит здесь. Можете подсказать в чем я ошибся или же есть другие более БЫСТРЫЕ алгоритмы. Заранее Спасибо!

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Зачем там дерево отрезков... Всё делается в массиве префикс-сумм (описание есть на е-маххе).

Насчёт алгоритмов — есть алгоритм Манакера, например. (статья о нём тоже есть на е-маххе) Можно также использовать суффиксное дерево (или суффиксный автомат) и LCA, но это сложнее.

И да, по моим наблюдениям у первых восьми тестов такой чекер, что они просто сверяют, что программа возвращает ноль.

→ Ответить