Discussion @ 1354. Palindrome. Again Palindrome @ Timus Online Judge

Help, please, I have AC.

Posted by Blum 22 Aug 2008 17:16

I've got AC constructing suffix tree (mcc algo). Now, who also has O(N) solution simplier than mine, please tell me your idea. And is O(N*N) anough to get AC? Thanks.

Re: Help, please, I have AC.

Posted by [SPbSU ITMO] WiNGeR 22 Aug 2008 17:50

This problem can be solved in O(n) by KMP algorithm.
http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm

Re: Help, please, I have AC.

Posted by Blum 23 Aug 2008 12:32

Oh, yes. How stupid I was. Thanks a lot. Now I have AC with kmp)

Re: Help, please, I have AC.

Posted by Vladislav Ivanishin 2 Jul 2009 00:51

Blum wrote 22 August 2008 17:16

I've got AC constructing suffix tree (mcc algo). Now, who also has O(N) solution simplier than mine, please tell me your idea. And is O(N*N) anough to get AC? Thanks.

yes. It is a little strange, but O(n^2) really gets AC

Re: Help, please, I have AC.

Posted by Andrew Shmig aka SKYDOS [Vladimir SU] 16 Jul 2010 15:46

How to solve this problem using KMP? Somthing with prefix function or what?
Help me pls, 'cause I solved this only with O(n^2).

Discussion of Problem 1354. Palindrome. Again Palindrome