Biológiai alkalmazásokban gyakran össze akarjuk hasonlítani két vagy több élőlény DNS-ét. A DNS-t bizonyos, bázisnak nevezett molekulák szekvenciái alkotják. A lehetséges bázisok: adenin, guanin, citozin és timin. A bázisokat a kezdőbetűjükkel jelöljük. A DNS szerkezet leírható a véges {A,C,G,T} halmazból képzett sorozattal.
Gyakran szükség van két élőlény DNS-ének összehasonlítására. A hasonlóság egy lehetséges mértéke, hogy megkeressük a leghosszabb olyan (nem feltétlenül szomszédos) bázisokból álló sorozatot, ami mindkét DNS-ben (azonos sorrendben) szerepel.
Feladat
Írj programot, amely beolvas két DNS kódot, és megadja a leghosszabb közös részsorozat hosszát, továbbá kiír egy ilyen hosszú közös részt.
Bemenet
Az lkre.be állomány két sorból áll, mindkét sor egy legfeljebb 100 karakterből álló kódot tartalmaz.
Kimenet
Az lkre.ki állomány első sorába a leghosszabb közös részsorozat hosszát, a másodikba pedig egy ilyen sorozatot kell írni.
Példa
| Bemenet |
Kimenet |
| ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
GTCGTTCGGAATGCCGTTGCTCTGTAAA |
20
GTCGTCGGAAGCCGGCCGAA
|
Tesztadatok
Címkék
A feladat forrása: olimpiai selejtező ?
Algoritmusok: dinamikus programozás
megoldás
| 
2004-2016 BDG algoritmus szakkör
