Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_08_04 - Szpieg u bram wioski

Jasio nadal kontynuuje swoją wielką kampanię w ulubionej grze strategicznej. Wciąż toczy zaciętą walkę z potężnym Zbójem i czuje, że powoli traci przewagę. Jak do tej pory, szpiedzy Jasia bezskutecznie próbują przedostać się do wiosek przeciwnika i zdobyć informacje, które pozwoliłyby naszemu bohaterowi pokonać wroga. Problem jest tego typu, że gdy szpieg zbliża się do bram wioski, słyszy pewne niezrozumiałe słowo i żeby wejść do środka musi prawidłowo podać pasujące do słowa hasło. Jasiu dowiedział się z pewnego źródła, że Zbój cierpi na chorobę, która się zwie "aibohphobia" - lęk przed palindromami. Palindrom to wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej np.:

"a kilku klika", "asa loguj u golasa" czy "julu, mysz sama, masz, symuluj". 

Z innego źródła dowiedział się, że hasłem może być liczba, która reprezentuje ilość liter najdłuższego podciągu, który jest palindromem.

Pomóż ponownie naszemu strategowi i napisz program, który być może rozwiąże wszystkie problemy Jasia.

Wejście

Nieokreślona ilość wierszy. Każdy wiersz składa się z n małych liter języka angielskiego (n ≤ 104). 

Wyjście

Dla każdego wiersza jedna liczba określająca ilość znaków przypadająca na najdłuższy palindrom spełniający kryteria zadania.

Przykład

Input:
algoliga
kokosek
macbon
witman
damians
adambak
narbej
mrozik
mariosoft
kaspro

Output:
5
5
1
1
3
3
1
1
3
1

Dodane przez:Marcin Kasprowicz
Data dodania:2013-06-27
Limit czasu wykonania programu:1s-25s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All

ukryj komentarze
2014-02-25 12:55:10 Ostry
>>Mi nie przechodzi standardowe rozwiązanie O(n^2/2), mimo, że dołożyłem "wycinanie" z obliczeń wspólnego początku/końca napisu. Wciąż TLE. <<

Już ok, limity są dość wąskie, jedna operacja dodawania w pętli dużo zmienia ;)



Ostatnio edytowany: 2014-02-25 13:16:33
2013-08-08 17:54:22 Marcin Kasprowicz
A dokładniej (n^2)/2
2013-08-08 17:03:37 Lupus Nocawy
Nie wiem czy nie lepiej przenieść to pytanie na forum :D
Ale O(n^2).
2013-08-08 14:39:38 Marcin Augustynowicz
Jaka jest wzorcowa złożoność do tego zadania?
2013-07-25 15:19:23 Marcin Górka
edit
@down
W sumie masz rację

Ostatnio edytowany: 2013-07-25 19:46:42
2013-07-25 00:19:18 Lupus Nocawy
Podciąg nie musi być spójny.
algoliga -> alola

edit: @up: podciąg z definicji nie musi być spójny.

Ostatnio edytowany: 2013-07-25 17:37:20
2013-07-24 21:00:59 Marcin Górka
Gdzie w słowie "algoliga" jest palindrom? Bo za Chiny nie mogę go dostrzec, a na wyjściu, ma niby 5 liter. To samo w drugim, jedyny palindrom, który dostrzegam to "oko". Chyba, że zadania nie zrozumiałem.

Ostatnio edytowany: 2013-07-24 21:01:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.