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
_______________________________________________
Brmlab mailing list
[email protected]
http://rover.ms.mff.cuni.cz/mailman/listinfo/brmlab
