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