 |
Az S. 9. feladat (2005. május) |
S. 9. Manapság bárki letölthet különböző DNS mintákat az internetről. Egy-egy ilyen leírás leegyszerűsítve a bázisok rövidítéseinek felsorolásából áll, tehát az ,,a'' ,,c'' ,,g'' és ,,t'' betűkből. Feladatunk most egy ilyen leírásban (amiben tehát csak az a, c, g, t betűk szerepelnek) keresni egy sorozatot (pl. egy gént). A leírást és a keresendő mintát egy-egy szövegfájlban adjuk meg. Mindkét fájl első sorában a betűk száma áll, ezután következik az a, c, g, t betűkből álló sorozat, amit az olvashatóság kedvéért legfeljebb 100 hosszúságú sorokra tördelünk.
A program a parancssorban kapja meg a szükséges fájlneveket; előbb a leírást, másodszor pedig a mintát tartalmazó fájl nevét. A program outputja a standard kimenetre: 0, ha a keresett minta nem szerepel, és i, ha a keresett minta első előfordulása az i-edik pozíción kezdődik. (A pozíciók számozását 1-től kezdjük.)
A leírásról feltehetjük, hogy maximum 50 millió, a keresett minta pedig maximum 1 millió betűből áll. Tesztadatok itt találhatók.
Példa:
| leiras.txt | minta.txt | A program futtatása |
50 agcgtagcatcgatccgata cgatggtgcacacggcatac gtacatcgct | 5 atcgc | 45 |
(10 pont)
A beküldési határidő 2005. június 15-én LEJÁRT.
Statisztika:
7 dolgozat érkezett. 10 pontot kapott: Engedy Balázs, Treszkai László. 9 pontot kapott: Deák 666 Áron, Vincze János. 8 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2005. májusi informatika feladatai