# Aplicatii teoretice si probleme de matematica :)
# Pattern matching

Se dau stringurile M si N. Se cere sa gasim toate aparitiile lui N in M.
Vom numi Mi prefixul lui M de lungime i. Presupunand ca avem construit automatul care accepta stringul N, vom cauta toate prefixele lui M acceptate de automat, deci toate numerele 1 <= i <= lungime(M) cu proprietatea ca automatul accepta stringul Mi.

Se dau stringurile $M$ si {$N$}. Se cere sa gasim toate aparitiile lui $N$ in {$M$}.
Vom numi {$M{~i~}$} prefixul lui $M$ de lungime {$i$}. Presupunand ca avem construit automatul care accepta stringul {$N$}, vom cauta toate prefixele lui $M$ acceptate de automat, deci toate numerele $1 ≤ i ≤ lungime(M)$ cu proprietatea ca automatul accepta stringul {$M{~i~}$}.

h2. Algoritm_potrivire_cu_automat_finit

h3. Algoritm_potrivire_cu_automat_finit

1: n = lungime(N)
2: q = 0;
3: pt i <- 1, n
4: q = d(q, M[i])
5: daca q apartine A
6: scrie "potrivire la pozitia " i - n + 1

== code(c) | n = lungime(N)
q = 0;
pt i <- 1, n
    q = d(q, M[i])
    daca q apartine A
        scrie "potrivire la pozitia " i - n + 1

complexitate : O(n)

* Complexitate : $O(n)$

Sa vedem cum se construieste automatul de potrivire pentru un string N. Fie m = lungime(M). Construim un automat cu m + 1 stari {q0, q1, ... qm}, A = {qm} . Faptul ca ne aflam in starea x inseamna ca au fost acceptate primele x caractere din sirul de intrare.
Din fiecare stare qx apartine Q si pt fiecare c apartine S construim d(x, c) = y cu proprietatea ca My este cel mai lung prefix al lui M care este sufix al lui Mxc (prefixul de lungime x al lui M, concatenat cu caracterul c).

h2. Algoritm_constructie_automat_finit

h3. Algoritm_constructie_automat_finit

1: m <- lungime(M)
2: pt q <- 0, m

8: k <- k + 1
9: p[i] <- k

h4. Analiza complexitatii :

Analiza complexitatii :

- la fiecare pas (i = 2, n) k se incrementeaza cel mult o data, deci pe parcursul algoritmului k se va incrementa de cel mult n - 1 ori (linia 8)
- in linia 5, k se decrementeaza cel mult pana devine 0, deci se va decrementa de cel
mult n - 1 ori pe parcursul algoritmului