ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1297. Палиндромы

O(N)
Послано sloboz 13 апр 2004 05:57
this can be done very cool in O(N) with Suffix Trees. Try it!
Re: O(N)
Послано Gheorghe Stefan 15 апр 2004 05:15
you maniac!
Re: O(N)
Послано mytest 26 апр 2004 22:03
What is the test #7? )
please tell me how do to it in O(n)
Послано Dilyan 2 июл 2004 15:29
write me to dpdokov@yahoo.com
or post you idia here
?!?!?!?!?!?!?!?!
Re: O(N)
Послано Tihon Sergey 10 янв 2007 02:29
Solution O(N^3) with some optimization AC 0.001
Re: O(N)
Послано Sandro (USU) 10 янв 2007 16:18
Your time is not so good after rejudge. :)
Re: O(N)
Послано Shadow of Death 17 окт 2007 23:16
Just O(2N)
Use Prefix Function!
Re: O(N)
Послано kima 21 ноя 2009 02:42
O(N) used hash function ;)
Re: O(N)
Послано Artem Khizha [DNU] 4 авг 2010 23:00
After all, I solved the problem by DP in O(N), counting the number of palindromes, though it is rather hard.

2 Shadow of Death:
I'm very interested in solution with prefix-function, would you be so kind to tell more about it? I'm a newbie in string-algorithms, but hope to learn them better.
Re: O(N)
Послано mabodx 7 сен 2010 06:59
if you have learned suffix arrays you can use that to solve these problem . it's not difficult
Re: O(N)
Послано Anuar 15 дек 2011 09:54
How did you do that?
Re: O(N)
Послано Soucup Adrian 27 июл 2012 19:05
Naive O( N ^ 2 ) = 0.015, 116 kb
Re: O(N)
Послано lichtgestalt2710 13 фев 2014 06:41
also this can be solved with Manacher's algorithm in O(N) =)
Re: O(N)
Послано lichtgestalt2710 13 фев 2014 06:41
also this can be solved with Manacher's algorithm in O(N) =)
Re: O(N)
Послано OIdiot 14 авг 2014 19:04
O(NlogN)?