[Brmlab] FreeStyle C0ding Contest

Vaclav Barta vbar at comp.cz
Wed Aug 17 08:36:05 CEST 2011


Hi,

problem specifikovany na http://brmlab.cz/project/coding_contest je znam coby  
"shortest common superstring". Je NP-uplny, ale existuji docela prakticke 
algoritmy pro priblizne reseni. Jeden (vicemene podle 
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.5258&rep=rep1&type=pdf 
) jsem si dovolil implementovat - je k dispozici na 
https://github.com/vbar/superstring . Neni to nijak zvlast optimalizovane 
(presneji receno, jemnejsi detaily toho algoritmu jsem vynechal :-) ), nicmene 
tech 10000 retezcu ze zadani to na mem laptopu schrousta za 40 sekund, coz by 
snad melo stacit...

	Bye
		Vasek



More information about the Brmlab mailing list