11. fejezet - Mintaillesztés

Bizonyos típusú adatoknál gyakran előfordul, hogy egy hosszabb szövegben kell megkeresni egy minta összes előfordulását. Feltesszük, hogy a szöveget a T[1..n] tömb tartalmazza, míg a mintát a P[1..m] tömb. Mindkét tömb elemei egy adott véges ábécé elemei. Azt modjuk, hogy a P minta a T szövegben s eltolással előfordul, ha minden 1 i m értékre P[i] = T[s + i]

11.1. Brute force (nyers erő)

A legegyszerűbb módszer esetén a mintát - mint egy sablont - végigtoljuk a szövegen, s ellenőrizzük, hogy a minta jelei megegyeznek-e a szöveg megfelelő jeleivel. A 1. táblázat mutatja az algoritmust futását. A táblázatból leolvasható, hogy 1 eltolással a minta illeszkesdik a szövegre. A két egymásba ágyazott ciklusnak

11.1. táblázat - 1. táblázat. Brute force algoritmus


megfelelően a bonyolultság O(nm). A brute.htm állomány egy olyan programot tartalmaz, amely véletlen módon generált szövegre és mintára végrehajta a Brute force módszert. A pontok jelzik a teljes szöveget, a számok a minta illesztését a teljes szövegre. Ha a minta illeszkedik, akkor az a program zölddel jelzi.