Vyhledávání nejdelšího opakujícího se substringu v txt souboru – Java – Fórum – Programujte.com

Nazdárek!

Chtěl bych vás, zkušené programátory poprosit o pomoc. Mám za semestrální práci (která mi byla přidělena) txt soubor s miliónem znaků "a g c t" random seřazené (začíná to např "aggctaatgctat") a já mám nalézt nejdelší opakující se substring a vypsat, kde se všude v tomto obrovském řetězci nachází.

Můj problém je, že jsem kdysi dělal v jiném jazyku brutal force na krátké řetězce, ale to je pro tento případ nepoužitelné, protože to, jestli jsem prošel nebo ne závisí na rychlosti, jak rychle se to celé provede....

Jsem nový obor, který nemá v prvním semestru algoritmizaci, takže jsem celkem ztracen...

Dokázal by někdo tento problém vyřešit? Byl bych moc vděčný....



PS: Napadlo mě si vytáhnout z toho zdrojového souboru souřadnice, kde se nachází jaké písmenko. Poté si udělat pár vyhodnocovacích cyklů, které porovnají substringy začínající těmito indexy a koukne se, co od 0tého prvku mají společné a to vezmou jako prozatimní nejvyžsí prvek. Zkoušel jsem toto naprogramovat, ale nepodařilo se mi to...nejsem tak zběhlý v programování.... A teď, když nad tím tak přemýšlím je to (asi) jen převlečený brutal force :(

To dreIx : Já bych postupoval tak, že bych ten string dělil pořád na poliviny a tim prvním dílkem bych pořád porovnával zbytek toho stringu dokola. Ale asi to nebude "nejrychlejší řešení".

Ale taky by mě zajímalo jak má být vyhodnocen tento řetězec:

"acaca"

Jako dvakrát se opakjící se "ac" nebo dvakrát opakující se "aca" (podřetezce se můžou překrývat) ?

To d.mostek : Kdyby se řetězce mohly překrývat, tak je tam jedna velká shoda.

Mě to spíš evokuje buď korelační metody nebo slovníky (něco na způsob LZ komprese).

To liborb : Nemusel by být s podmínkou že překryv je aspoň o 1 políčko posunut.

Myslím že tvoj problém sa týka dynamického programovania, konkrétne longest common subsequence[substring].
viď google[1] alebo presne tvoj problém[2] :smile1:

[1] http://www.google.sk/search?hl=sk&rlz=1C1GGLS_skSK304SK304&q=longest+common+subsequence&btnG=H%C4%BEada%C5%A5&meta=&aq=f&oq=
[2] http://www.cs.sunysb.edu/~algorith/files/longest-common-substring.shtml

Děkuji moc :smile1:
Myslím, že jakž takž tuším o co jde, ale.... byl by nějaký hodný coder napsat nějakou obecnou sekvenci toho, co dělat? Sám moc nevím, jak začít a směrovat to správným směrem a jsem už celkem zoufalý :(

Nechcu delat vlny, ale longest common subsequence to urcite nebude. To vyhledava 1 nejdelsi v mnoha vstupech a problem je najit mnoho v 1 vstupu. Spis bych to videl na Suffix tree a ten potom prjit. vice: http://en.wikipedia.org/wiki/Suffix_tree http://www.allisons.org/ll/AlgDS/Tree/Suffix/