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

AnhDQ My idea for O(n) but wrong for test #5 [4] // Задача 1297. Палиндромы 30 апр 2008 17:57

F[i]: the longest Palindrom ended at St[i]
Cont[i]: the number of continue same characters with St[i], ended at St[i]

if St[i] = St[i - F[i - 1] - 1] then
F[i] = F[i - 1] + 2
else
if St[i] = St[i - 1] then
F[i] = Cont[i];

The result is Max(F)

What's wrong with it ???

Alias aka Alexander Prudaev Re: My idea for O(n) but wrong for test #5 // Задача 1297. Палиндромы 30 апр 2008 19:47

aabbbaabbb
it is wrong algorithm

wwwaaannngggrs Re: My idea for O(n) but wrong for test #5 [2] // Задача 1297. Палиндромы 15 июл 2010 15:22

The only O(n) Algotithm is suffix tree+LCA
or Suffix array + +-1RMQ+LCA+Catersian Tree

AnhDQ писал(a) 30 апреля 2008 17:57

Hristian Hristov Re: My idea for O(n) but wrong for test #5 // Задача 1297. Палиндромы 8 окт 2011 19:28

That's wrong! There's another O(n) algorithm. It's called Manacher's algorithm.

Hristian Hristov Re: My idea for O(n) but wrong for test #5 // Задача 1297. Палиндромы 9 окт 2011 02:10

Edited by author 09.10.2011 02:10

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