Макар и трудно построяването на суфиксно дърво на зададен низ може да се направи със сложност O(N). На http://www.math.tau.ac.il/~haimk/seminar00/ могат да се намерят презентации свързани с построяването на суфиксно дърво,а на http://dogma.net/markn/articles/suffixt/suffixt.htm да се прочете една добра статия на същата тема. Най-лесен за имплементация е алгоритъмът на E. Ukkonen. За нашата задача ще е необходимо т.н. обобщено суфиксно дърво на S и S ^r -обратния на S. Това е суфиксно дърво за суфиксите едновременно на S и S ^r, като за да се различават суфиксите на S от тези на S ^r, се вземат различни завършващи знаци, например $ и #. За решението ще ни е необходимо и следното понятие: НОП или най-близък общ предшественик (LCA - Lowest Common Ancestor) на два върха в кореново дърво T наричаме връх, които лежи на всеки от пътищата от тези върхове до корена и е най-отдалечения от корена такъв връх. На фигурата, НОП за лист 2 и лист 5 е върха с конкатенация “bcabc” на надписите по ребрата, намиращи се на пътя от корена до него. Да означим с НОП(L_a,L_b) дължината на низа, който е конкатенация на надписите на ребрата по пътя от корена на суфиксно дърво до НОП на листата L_a и L_b. За разгледания пример НОП( L(S,2), L(S,5) ) = 5. НОП(L_a,L_b) може да се реализира със сложност O(1), като изисква предварителна обработка със сложност O(|VT|), където VT е множеството от върхове на суфиксното дърво, като|VT| = O(N). В решението на журито бе използван алгоритъмът на Schieber и Vishkin. Някои от участниците използваха алгоритъм за решаване на задачата, известна като RMQ (Range Minimum Query), която е пряко свързана с LCA. За подробности относно RMQ, виж http://www.scs.carleton.ca/~morin/teaching/tds/refs/bf-c00.pdf . За решението на първата част на задачата може да се използва следният алгоритъм:

• 1. Построяваме обобщено суфиксно дърво T на S и Sr;
• 2. Намираме нечетните мв-палиндроми по следния начин: за всяко K=2,3,…,N-1, пресмятаме d=НОП(L(S,k+1), L(S ^r,N-K+2)). Ако d>0 имаме нечетен палиндром с начална позиция K-d и крайна позиция K+d.
• 3. Намираме четните мв-палиндроми по следния начин: за всяко K=1,2,…,N-1, пресмятаме d=НОП(L(S,k+1), L(S ^r,N-K+1)). Ако d>0 имаме четен палиндром с начална позиция K+1-d и крайна позиция K+d.

За по-бързо решение на втората част на задачата ще използваме също НОП. Нека d = НОП(L_X,L_Y), където L_X е листът в Т, съответстващ на суфикса, на който X е префикс; аналогично за L_Y. Да дефинираме функцията Less(X,Y) с аргументи мв-палиндромите X и Y, с дължини d_X и d_Y, която връща стойност истина, ако X е лексикографски преди Y и неистина - в противен случай:

• Ако d_X < d, тогава Less := d_X < d_Y;
• в противен случай ако d_Y < d, тогава Less := false;
• в противен случай Less := DFS(L_X) < DFS(L_Y).

Като DFS(v) ни дава номера на v при preorder-обхождането на T в дълбочина, при което наследниците на текущия връх се обхождат в ред съответстващ на лексикографската наредба на изходящите ребра. Да отбележим само, че DFS номерирането е част от работата на алгоритъма на Schieber и Vishkin и не изисква допълнително време. Така сравняването на два мв-палиндрома става за константно време и втората част на задачата се реализира със сложност O(M).По този начин получаваме за цялата задача алгоритъм със сложност O(N+M)=О(N). Контстантите на този алгоритъм, разбира се, не са малки, но той може да се реализира за разумно време (3-4 дни) и е много ефективен. И все пак имаме участник, които без да се задълбочава в споменатите по-горе теории е успял да напише решение, което е много по-добро от решенията на останалите участници. Случайно или не, това е победителят от първия кръг от задочната част на Конкурса - Камен Добрев. Решението, според автора, използва техниката “Разделяй и владей” и описанието му може да се намери тук.