A szöveg alapú mintaillesztés feladata hosszú karaktersorozatokban meghatározott szövegrészek helyének megkeresése. A feladat, bár elsőre egyszerűnek hangzik, nagyméretű bemenetek esetén memóriában és futási időben is kihívást jelent. Ezeknek az algoritmusoknak sok felhasználási területe van nyelvfeldolgozás, a keresőmotorok, vagy akár a bioinformatika területén.
A mintaillesztés általános esetben kétféle módszerrel végezhető el. Az egyik ilyen, amikor a bemeneti szövegre illesztjük a mintánkat. A másik eset pedig az, amikor a szövegen ún. előfeldolgozást végzünk el, mivel többször is szeretnénk keresést végrehajtani. Az előfeldolgozás segítésével egy adatstruktúrát építünk a szövegből. A legismertebb adatstruktúrák a szuffix tömbök és a szuffix fák.
A párhuzamos programozással egy problémát felosztva több részre, elérhető, hogy több feldolgozási egység dolgozzon a saját részén egyszerre a többivel. Régebben a processzorok órajelének növelése volt az alapja annak, hogy egy program futásának az idejét csökkentsék, de ma már a teljesítmény növelésének érdekében a programok párhuzamosítása vette át a vezető szerepet.
Felmerül tehát a kérdés, hogy a mintaillesztéses algoritmusok mivel nagyméretű adatokkal dolgozhatnak, milyen mértékben és feltételek mellett párhuzamosíthatók
A dolgozatomban bemutatom mélyebben a szuffix tömbökre épülő mintaillesztéses algoritmusokat, illetve ezek párhuzamosítási lehetőségeit CPU-n illetve GPU-n is.