String keresés (KMP)

Klasszikusnak számító keresési feladat, melynek során egy szövegben keresünk egy szót. A jelen feladatban a szó első előfordulását keressük, azzal a kiegészítéssel, hogy a keresendő szó tartalmazhat "JOKER" karaktereket. Nevezzük JOKER karaktereknek a '*' és a '?' karaktereket, ahol a '?' pontosan egy tetszőleges karakterrel egyenértékű, a '*' tetszőleges hosszú, (akár nulla hosszú) tetszőleges karakterrel egyenértékű helyettesítő karakterek. Tehát nem is egy szó, hanem egy minta első előfordulását keressük. A feladat megoldására használjuk a Knuth-Morris-Pratt algoritmus "megfelelően" módosított változatát.

Bemenet:

Az INPUT.TXT tartalmazza a szöveget, amelybe keressük a mintát. Az egyszerűség kedvéért, a szöveg az angol abc alfanumerikus karaktereiből áll. A program a standard inputról várja a keresendő mintákat.

Kimenet:

A program a standard outputra írja a válaszokat. A válasz kétféle lehet. Amennyiben nem fordul elő a minta a szövegben, a válasz "Nem fordul elo!". Amennyiben előfordul, az első előfordulást kell megadni a következőképpen: minden nem JOKER karakter szövegbeli pozícióját felsoroljuk vesszővel elválasztva. (A szöveget karaktereinek pozícióját 1-től kezdve sorszámozzuk.)

Példa:

 

A szöveg:         AAABBBAACCCCAAABBABBBAAAABBC.

 

 

(Nagy Tibor)