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 <feher_g@freemail.hu>
To: acm-valogato@cs.bme.hu
Subject: Re: [acm-valogato] acm-felkeszites - feladat
Message-ID:
       <328f8b410909201431v2e1006e9y42ff8ae782aeb07f@mail.gmail.com>
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-in-linear-time/

Ett?l f?ggetlen?l szeretn?m meg?rteni M?t? verzi?j?t is!

G?bor



2009/9/17 Ildi Schlotter <schlotterildi@gmail.com>:
> Sziasztok,
>
>
> Mate kuldott egy feladatot (koszonjuk!), lehet rajta gondolkodni holnapig:
>
>> Adott egy maximum 10^4 hosszu string (mondjuk az angol abc kisbetuibol).
>> Keressuk meg a leghosszabb palindrom-reszstringjet.
>
> Ildi
> _______________________________________________
> acm-valogato mailing list
> acm-valogato@sziami.cs.bme.hu
> http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
>