(Creat de '_azotlichid_':user/azotlichid la data de _2005-01-12_ categoria _Automate_, autor(i) _Vladu Adrian_)
*Continut scurt:*

 In acest articol vom aborda cele mai comune probleme legate de pattern matching si vom oferi suportul teoretic necesar intelegerii algoritmului Knuth-Morris-Pratt, pornind de la potrivirea standard cu automate finite si rafinand-o treptat pana la un algoritm de complexitate O(n + m). Toate acestea intr-o maniera usor de inteles ;)

 ==Include(page="template/raw")==
 
In acest articol vom aborda cele mai comune probleme legate de pattern matching si vom oferi suportul teoretic necesar intelegerii algoritmului Knuth-Morris-Pratt, pornind de la potrivirea standard cu automate finite si rafinand-o treptat pana la un algoritm de complexitate O(n + m). Toate acestea intr-o maniera usor de inteles ;)

*Continut lung:*

==Include(page="template/raw")==
 

Automate finite
Ce sunt automatele finite ?

2: k <- 0
3: p[1] <- 0
4: pt i <- 2, n

5: cat timp (k > 0) si (N[k + 1] Â?? N[i])

5: cat timp (k > 0) si (N[k + 1] ** N[i])

6: k <- p[k]
7: daca N[k + 1] = N[i]
8: k <- k + 1

1: m <- lungime(M), n <- lungime(N)
2: q <- 0
3: pt i <- 1, m

4: cat timp (q > 0) si (N[q + 1] Â?? M[i])

4: cat timp (q > 0) si (N[q + 1] ** M[i])

5: q <- pi[q]
6: daca N[q + 1] = M[i]
7: q <- q + 1