Il pattern matching si occupa di ricercare un pattern $P$ in un testo $T$. Si hanno:
Defnizione: Definiamo “stringa” come una sequenza di simboli appartenenti ad un dato alfabeto $\Sigma$, scritta come:
$$ X = x_1, ..., x_n, \ \forall x \in \Sigma $$
ovviamente non è necessario che la stringa contenga tutti i simboli dell’alfabeto.
Diamo alcune definizioni utili:
$|X|$ indica la lunghezza della stringa
$\epsilon$ indica la stringa vuota
$X[i]$ indica il caratterre all’indice $i$ (partendo da 1 e non da 0)
$X[i, j]$ indica la sottostringa che parte dall’indice $i$ e arriva all’indice $j$ (estremi inclusi). Inoltre se si hanno $i \neq j$ e $j \neq |X|$ si ha una sottostringa propria.
(Es: $X = bbaccbbaac$ ho la sottostringa $X[4, 8]= ccbba$)
$X[1, j]$ indico un prefisso (estremo finale incluso). Si ha ll prefisso proprio se $j \neq |X|$ e si ha prefisso nullo se $j = 0$ e si indica con $\epsilon$.
(Es: $X = bbaaccbbaac$ ho il prefisso $X[1,4] = bbac$)
$X[i, |X|]$ indica un suffisso della stringa lungo $k = |X| - i + 1$, avendo quindi il suffisso $X[|X|-k+1, |X|]$. Si ha inoltre che se ho $X[|X|, |X|+1]$ allora ho il suffisso nullo, ovvero $\epsilon$.
(Es: $X[8,10]=aac$ e il suffisso $X[11, 10]=\epsilon$, stringa di prima)
Definizione: Definiamo il pattern matching esatto come la ricerca di tutte le occorrenze esatte di un pattern $P$ in un testo $T$.
$P$ occorre esattamente in $T$, a partire dall’indice $i$ in $T$, sse:
$$ T[i, i+|P|-1] \text{ coincide con } P $$
Quindi in output ho tutte le posizioni $i$ nel testo tali per cui