Algoritmo di pattern matching su stringhe

In Informatica gli algoritmi di pattern matching su stringhe, a volte chiamati algoritmi di confronto fra stringhe o algoritmi di ricerca di stringhe, sono una classe importante degli algoritmi sulle stringhe che provano a individuare una posizione all'interno di una stringa più grande o di un testo, in cui una o più stringhe solitamente più piccole (dette anche pattern) si trovano.

Sia Σ un alfabeto (formato da elementi appartenenti a un insieme finito). Formalmente, sia il pattern cercato che il testo su cui è effettuata la ricerca sono vettori di elementi di Σ. Σ può essere un alfabeto umano comune (per esempio, le lettere dalla A alla Z nell'alfabeto Latino). Altre applicazioni possono usare un alfabeto binario (Σ = {0,1}) o un alfabeto del DNA (Σ = {A,C,G,T}) in bioinformatica.

Nella pratica, il modo in cui le stringhe sono codificate può influenzare la fattibilità degli algoritmi di ricerca di stringhe. In particolare se usiamo una codifica a lunghezza variabile allora l'algoritmo sarà lento (in termini di tempo proporzionale a N) per trovare l'N-esimo carattere. Questo rallenterà significativamente molti dei più avanzati algoritmi di ricerca. Una soluzione possibile è invece cercare la sequenza di unità di codice (codeword): così facendo si potrebbero però produrre falsi riscontri se la codifica non fosse appositamente progettata per evitarli.