Обсуждение @ 1354. Палиндром. Он же палиндром @ Timus Online Judge

Help, please, I have AC.

Послано Blum 22 авг 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.

Послано [SPbSU ITMO] WiNGeR 22 авг 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.

Послано Blum 23 авг 2008 12:32

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

Re: Help, please, I have AC.

Послано Vladislav Ivanishin 2 июл 2009 00:51

Blum писал(a) 22 августа 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.

Послано Andrew Shmig aka SKYDOS [Vladimir SU] 16 июл 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).

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