Szövegszerkesztő programokban gyakori feladat megkeresni egy szövegben egy
minta összes előfordulását. A szöveg rendszerint a szerkesztendő dokumentum, a keresendő
minta
pedig a felhasználó által megadott szó.
A mintaillesztési probléma a következőképpen fogalmazható meg. Tegyük fel,
hogy a szöveget egy $n$ hosszúságú $T : \sum[n]$ nullától indexelt tömb tartalmazza, a mintát pedig az $m$
hosszúságú $P : \sum[m]$ nullától indexelt tömbben tároljuk, és $m \leq n$. Mindkét tömb elemei a $\sum$ véges ábécé
jelei. A mintaillesztési probléma megoldásakor egy adott $P$ minta összes érvényes eltolását kell
megtalálnunk. Ha $P$ előfordul $s$ eltolással $T$-ben, akkor $s$ érvényes eltolás, ellenkező
esetben $s$ érvénytelen eltolás. Az érvényes eltolások halmaza:
$S = \{ s \in 0..(n-m) \space | \space T[s ..s + m) = P[0..m) \}$
A mintaillesztő algoritmusok első lépésben valamilyen módon feldolgozzák a
mintát, és ezután találják meg az érvényes eltolásokat. Az első lépést előfeldolgozásnak, a
második részt illesztésnek nevezzük.
Jelölések:
- $T:\sum[n]$ $T$ nevű, nullától indexelt, $n$ méretű karakterek tömbje, ez a szöveg
amelyben
keresünk
- $P:\sum[m]$ $P$ nevű, nullától indexelt, $m$ méretű karakterek tömbje, ez a szöveg amelyet
keresünk $T$-ben
- $s \in 0..(n-m)$ természetes szám, amely egy eltolást határoz meg
- $S : \mathbb{N} \{\}$ érvényes eltolások halmaza
- $\underline{B}$ az aláhúzás jelenti azt, hogy sikeres volt a mintaillesztés
- $\cancel{B}$ az áthúzás jelenti azt, hogy sikertelen volt a mintaillesztés