Nejdelší nejvíce se opakující řetězec.

[Folkow]

Ahoj,
momentálně řeším práci do školy, jejíž zadání jest napsat v Javě program, který, najde nejdelší opakující se podřetězec (maximálně 30 znaků) v řetězci, skládajícího se z milionu znaků, v co nejkratší době.

Prý se dá napsat takový program, který to zvládne za <= 3 sek.

Většina řešení, která mě napadla, byla tupá, přičemž jejicht složitost byla exponenciální, tudíž nepoužitelná.

Pátral jsem dál a narazil jsem na suffixové stromy, které řeší tento problém s lineární složitostí, ale zrovna dvakrát jsem to nepochopil.

Existuje nějaká metoda, se kterou bych to případně vyřešil s logaritmickou složitostí?

Děkuji moc a rád uvítám Vaše rady a jakékoliv jiné příspěvky, které by mi mohly pomoct.


_________________
http://www.e-telka.cz | http://www.iphonethemeszone.com

[OndraSej]

Ano, suffixove stromy by to mohly resit efektivne.

Ne, logaritmicky algoritmus neexistuje a ani existovat nemuze... jak bys chtel vyhledat vsechny podretezce bez toho, abys ten retezec aspon jednou precetl?
_________________
http://trionteam.net

[Quiark]

Suffixové stromy nebo pole nejsou vůbec složité a mohly by se hodit. V podstatě si uděláš seznam všech sufixů (to je triviální):

[tom.drin]

Přesně tuhle ulohu jsem řešil před rokem. (Nemáš náhodou Blocha?)
Asi né uplně šikovný řešení, ale můžeš si rozsekat vstup na stejně dlouhý překrývající se řetězce, seřadit je, odstranit unikátní a ty zbylý rozšířit o následující znak. Tohle opakuj dokud ti nezbudou jen ty nejdelší.

[Folkow]

Je tomu tak, ať žije Mr. Bloch. Jakým způsobem jsi to řešil ty?
_________________
http://www.e-telka.cz | http://www.iphonethemeszone.com

[Houp]

Naštěstí dělám "normální" semestrálku.. tuhle bych řešil stylem, najít si někoho, kdo z toho měl A, okopčit to, občas trochu někde něco změnit a hotovo.

Jinak bacha na ten limit, co jsem slyšel, tak ty 3s to musí dát na dost starém stroji(jen několik set MHz procesor), takže když tobě to udělá pod sekundu, tak to ještě nemusí znamenat, že to udělá včas i jeho stroj.
_________________

[Folkow]

Ano, to máš pravdu, ale ikdyby to bylo nad 3 sekundy, tak stejně dostanu zápočet, akorát nebudu superliga no..
_________________
http://www.e-telka.cz | http://www.iphonethemeszone.com

[Yossarian]

[Folkow]

[Houp]

[tom.drin]

[Folkow]

[pcmaster]

Bacha aby to nebolo tak, ze to pani na FELe zmenili prave preto, aby nachytali tych, co odovzdaju minulorocne riesenia
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[Alenka]

offtopic: Nechodis nahodou na FEL? ja jen ze spoluzak ma podobnou semestralku jeste ze tohle me minulo

EDIT: Priste si blbko precti celej post nez neco napises odpovedela jsem si sama po tom, co jsem si v jednom postup recetla jmeno "Bloch" brrr

[Folkow]

Jsem s Tondou ve skupině ...
_________________
http://www.e-telka.cz | http://www.iphonethemeszone.com