17 Aug
2011
17 Aug
'11
8:36 a.m.
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... ) 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