Vyhledávání nejdelšího opakujícího se substringu v txt souboru – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
dreIx0
Duch
29. 11. 2009   #1
-
0
-

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 :(

Nahlásit jako SPAM
IP: 147.32.122.–
Reklama
Reklama
d.mostek0
Návštěvník
30. 11. 2009   #2
-
0
-

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) ?

Nahlásit jako SPAM
IP: 85.13.98.–
www.dominik-mostek.cz
liborb
~ Redaktor
+18
Guru
30. 11. 2009   #3
-
0
-

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).

Nahlásit jako SPAM
IP: 85.207.166.–
d.mostek0
Návštěvník
30. 11. 2009   #4
-
0
-

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

Nahlásit jako SPAM
IP: 85.13.98.–
www.dominik-mostek.cz
Nosko0
Stálý člen
30. 11. 2009   #5
-
0
-
Nahlásit jako SPAM
IP: 84.16.37.–
dreIx0
Duch
30. 11. 2009   #6
-
0
-

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ý :(

Nahlásit jako SPAM
IP: 147.32.223.–
Krychlik
~ Anonymní uživatel
195 příspěvků
30. 11. 2009   #7
-
0
-

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/

Nahlásit jako SPAM
IP: 195.113.15.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 45 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý