Problem S. 58. (December 2010)
S. 58. The most spectacular event during the Annual Congress of Magicians is the contest of ``tall talks''. The winner is who can cast the longest magic spell consisting of a single word within a specified time limit, resulting in wonderful side effects.
Unfortunately, the contest proved to be a little too spectacular last year, and recovering the town took several months thereafter. To prevent such situations in the future, from now on magicians can only cast spells which can be written as a concatenation of some palindromes of even length, since these words are known to be harmless.
Your program should be able to prove whether a particular magic word is harmless by decomposing it, if possible, so it can be cast during the contest.
The first line of the standard input contains a single integer, the number N of magic words to be checked (1
N100), which are listed in the following N lines. Words contain only lowercase letters of the English alphabet. Each word is at most 1 000 000 characters long. Harmless words are built out of palindromes of length at most 5000.
The standard output should contain exactly N lines. The ith row should contain the evaluation of the ith magic word. If the word is harmless, first the number of palindromes K in its decomposition should be given (K
1), then elements of the decomposition should follow, separated by a space. If the decomposition is not unique, any of them can be displayed. If the word is maleficent, a ``0'' should appear.
In the example, ``Példa bemenet'' is sample input and ``Példa kimenet'' is the corresponding sample output.
The source code and project files of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (s58.txt, s58.pdf, ...) in a compressed folder s58.zip.
(10 pont)
Deadline expired on January 10, 2011.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás
Még ha egy részszóról gyorsan el is tudnánk dönteni, hogy tükörszó-e, akkor is felmerül a kérdés: hogyan tudunk hatékonyan meghatározni egy olyan felbontást, amelynek minden eleme tükörtulajdonságú?
Szerencsére a mohó módszer itt működik: megtehetjük, hogy a varázsszó egyre növekvő hosszúságú kezdőszeleteiről megvizsgáljuk, hogy tükör-e, és ha igen, levágjuk, majd a maradékra újból ugyanezt végezzük. Ha sikerül elfogyasztani a varázsszót, pontosan akkor biztonságos.
Ez helyes. Az egyedüli nehéz irány annak megmutatása, hogy ha van felbontás, akkor azt meg is találjuk. Ez pedig igaz, hiszen ha az algoritmusunk nem a felbontás első darabját, w-t találja meg, akkor annak egy v kezdőszeletét találhatta csak meg (hiszen növekvő hossz irányában dolgozik). Ha |v||w|/2, akkor w tükörtulajdonsága miatt w=vxx'v' alakú, ahol x w első felének azt a részét jelöli, melyet v nem fed le, az aposztróf pedig a tükrözés. Ekkor viszont a felbontásban w-t lecserélhetjük v, xx' és v'-re, hiszen egy tükörszó tükrözöttje is tükörszó, tehát van olyan felbontás is, melynek v az első eleme.
Hasonlóan, megmutatható hogy |v|>|w|/2 nem lehetséges, mert akkor már korábban kellett volna egy tükörszó kezdőszeletet találnunk.
Ezek után az egyetlen kérdés, hogy miként döntsük el egy kezdőszeletről, hogy tükörszó-e. Ezt Manacher jól ismert algoritmusával a varázsszó hosszában összesen lineáris időben meghatározhatjuk.
Statistics:
10 students sent a solution. 10 points: Barta 111 János, Borsos 607 Zalán, Szabó 928 Attila. 8 points: 4 students. 7 points: 1 student. 6 points: 2 students.
Problems in Information Technology of KöMaL, December 2010