Feladat: I.210 Korcsoport: - Nehézségi fok: -
Füzet: 2009/március, 167 - 168. oldal  PDF  |  MathML 
Témakör(ök): Feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

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