Az I. 210. feladat (2009. március)

I. 210. Egy szövegben egy szövegrészlet (minta) első előfordulásának megkeresésére kézenfekvő, bár lassú módszer az úgynevezett lineáris keresés: A keresendő minta első karakterét rendre a szöveg 1., 2., ...karakteréhez illesztjük, azaz a mintát végigléptetjük balról jobbra a szöveg felett mindaddig, amíg egy olyan illesztéshez nem jutunk, melynél a minta minden karaktere megegyezik a szöveg megfelelő karakterével.

Ha az ábécé a minta hosszához képest viszonylag számos, akkor jelentős gyorsulást érhetünk el a következő módszerrel: a keresendő mintát és a szöveget ismét csak balról jobbra hasonlítjuk össze, de ha az összehasonlítás közben különbséget találunk, akkor nem csak egy karakterrel léptetjük tovább (jobbra) a mintát, hanem a szöveg minta utáni első karakterétől függően akár többel is.

Ha ugyanis a szöveg minta utáni első karaktere egyáltalán nem fordul elő a mintában, akkor az összehasonlítást (mintaillesztést) biztosan elegendő az ez utáni karaktertől kezdődően folytatni.

Ha pedig a szöveg minta utáni első karaktere előfordul a mintában, akkor a minta eltolása az ábrán látható módon jobbról az első előfordulás illesztésével történik.

A végrehajtást gyorsítja, hogy a minta eltolása minden szövegben előforduló karakterre előre kiszámítható.

Írjunk programot, amely a parancssori argumentumban megadott szövegállományban megkeresi a billentyűzetről begépelt, legfeljebb 255 karakter hosszú szövegrészlet első előfordulását, és az azt tartalmazó mondatot a képernyőn megjeleníti. A mondat az előfordulást megelőző mondatvégi írásjel (,,.!?'' vagy fájlkezdete) utáni első nem szóköz karakterrel kezdődjön, és az előfordulás utáni első mondatvégi írásjellel vagy fájlvége jelnél fejeződjön be. A keresés során a kis- és nagybetűket ne különböztessük meg.

Beküldendő a program forráskódja (i210.pas, i210.cpp, ...), valamint a program rövid dokumentációja (i210.txt, i210.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2009. április 15-én LEJÁRT.

Megoldásokról

Viszonylag kevés maximális pontszám sikerült. Ennek oka, hogy sokan nem a megadott algoritmus alapján próbálták a megoldást elkészíteni. Többen nem vették figyelembe, hogy végrehajtást jelentősen gyorsítja, ha a minta eltolását minden előforduló karakterre előre kiszámítjuk. A tesztelést nagy méretű szövegállományon végeztük, hogy a hatékonyság különbségek futási időben is megjelenjenek. Erre Thomas Mann: József és testvérei című könyvét választottuk. (Ez letölthető a Magyar Elektronikus Könyvtárból.)

Minta megoldás

Englert Péter 12. osztályos (Zalaegerszeg, Zrínyi Miklós Gimnázium) megoldását közöljük. ( I210.pas)

Statisztika:

10 dolgozat érkezett.
10 pontot kapott:	Englert Péter, Kővágó Zoltán.
9 pontot kapott:	Uray Marcell János.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	2 versenyző.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2009. márciusi informatika feladatai