Programozás‎ > ‎Feladatok‎ > ‎

DNS

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