NézetNyomtat

DNS (Megoldás)
Címkék > Feladat

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

A DNS.BE állomány két sorból áll, mindkét sor egy legfeljebb 100 karakterből álló kódot tartalmaz.

Kimenet

A DNS.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

DNS.BE DNS.KI
ACCGGTCGAGTGCGCGGAAGCCGGCCGAA GTCGTTCGGAATGCCGTTGCTCTGTAAA 20 GTCGTCGGAAGCCGGCCGAA

Tesztadatok