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

Dilyan What can I use the KMP algorithm for ? [3] // Задача 1354. Палиндром. Он же палиндром 1 май 2005 00:16

not only in this problem. what can i use the KMP algorithm for? what kind of problems can i solve?

Dmitry 'Diman_YES' Kovalioff I solved no problems using exactly KMP, but... (+) [2] // Задача 1354. Палиндром. Он же палиндром 1 май 2005 09:21

You can try to solve Ural-1269. The problem is very difficult, use Aho-Corasik algo which is a modification of KMP for several substrings. And there are several problems I solved via finite automatons, in some of them you can use KMP. As for this very problem (Ural-1354) - O(N^2) solution is OK :)

Maigo Akisame (maigoakisame@yahoo.com.cn) Re: I solved no problems using exactly KMP, but... (+) // Задача 1354. Палиндром. Он же палиндром 11 май 2005 12:01

I'd like to know the solution to 1269. I use something I'd call trie-graph, and it works very well for 1158, but it takes up too much memory. Could you teach me the modified version of the KMP algo, or give me a link?

SPIRiT KMP is unnecessary here. // Задача 1354. Палиндром. Он же палиндром 28 авг 2006 12:50

As Dmitry Kovalioff stated before, O(N^2) solution works just fine. I found out empirically that 16 millions of operations fit just fine in one second. By the way, what was the jury idea? Was it really a trap task (seems hard with prefix functions, but quite simple with a little DP)? Or it's simply the time limit turned out to be too big?

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