Hi! A feladat linearis idoben megoldasa egy ismert feladat suffix tree-kkel kapcsolatban A megoldas benne van Dan Gusfield "Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology" cimu konyveben (201. oldal), a konyv joresze (tobbek kozt ez is) fent van Google Books-on Errol a megoldasrol viszont se azt nem latom, hogy helyes lenne, se pedig hogy linearis ideju, mondjuk lehet hogy csak azert nem bizok ebben, mert az ismert megoldas ennel joval bonyolultabb (Ukkonen-algoritmus es Lowest Common Ancestor-problema <O(n),O(1)> ideju megoldasa is kell hozza) De persze lehet hogy mukodhet, csak tul konnyunek tunik NGG Message: 1 Date: Sun, 20 Sep 2009 23:31:50 +0200 From: G?bor Feh?r &lt;feher_g(a)freemail.hu&gt; To: acm-valogato(a)cs.bme.hu Subject: Re: [acm-valogato] acm-felkeszites - feladat Message-ID: &lt;328f8b410909201431v2e1006e9y42ff8ae782aeb07f(a)mail.gmail.com&gt; Content-Type: text/plain; charset=ISO-8859-2 Sziasztok, megpr?b?ltam leprogramozni ezt az algoritmust, de elakadtam, ?s van egy k?rd?sem. J?l ?rtettem, hogy visszavezett?k a probl?m?t egy leghosszabb ism?tl?d? r?szstring keres?s?re? P?ld?ul: ha "abcvucbaww"-ben keres?nk leghosszabb r?szpalindromot, akkor ehelyett "abcvucbaww$wwabcuvcba" -ban keres?nk leghosszabb ism?tl?d? r?szstringet? Ezzel az a probl?m?m, hogy ?gy az eredm?ny "abc" vagy "cba" lesz a helyes "zz" helyett. Sz?val val?sz?n?leg rosszul ?rtettem. Konkr?tan az nem vil?gos, hogy mit csin?lunk, amikor elk?sz?lt a "gyors?t?t?mb?nk". Viszont, line?ris id?ben is megoldhat? a probl?ma! Ezt ?ll?t?lag n?gy h?napig tartott kital?lni egy PhD hallgat?nak, ?hgyhogy nem j?v?heti feladatnak aj?nlom, hanem belinkelem a megold?st: http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-i… Ett?l f?ggetlen?l szeretn?m meg?rteni M?t? verzi?j?t is! G?bor 2009/9/17 Ildi Schlotter &lt;schlotterildi(a)gmail.com&gt;om>: