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 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 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.