h1. Automate finite si KMP

(Categoria _Automate_, autor(i) _Vladu Adrian_)

(Categoria _Algoritmi_, Autor _Adrian Vladu_)

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 ;)

* $k = 2; δ(2, b) = 0;$
* $k = 0; δ(0, a) = 1;$
* $k = 1; δ(1, b) = 1;$

* $k = 2; δ(1, a) = 3;$

* $k = 1; δ(1, a) = 3;$

Daca ultima stare obtinuta $q{~k~}$ apartine {$A$}, atunci spunem ca automatul accepta stringul. Altfel spus, daca avem stringul {$s$}, {$lungime(s) = n$}, automatul accepta stringul daca si numai daca $δ( ... δ( δ(0, s{~1~}), s{~2~} ) ..., s{~n~} )$ apartine {$A$}.

== code(c) |
n = lungime(N)

m = lungime(M)

q = 0;

pt i <- 1, n

pt i <- 1, m

    q = d(q, M[i])
    daca q apartine A
        scrie "potrivire la pozitia " i - n + 1

h2. Teme pentru acasa:

* folosind functia prefix, rafinati constructia automatului finit de acceptare pt un string, aducand-o la complexitatea $O(m^2^ * |Σ|)$

* folosind functia prefix, rafinati constructia automatului finit de acceptare pentru un string, aducand-o la complexitatea $O(m^2^ * |Σ|)$

* problema "Microvirus":http://www.liis.ro/%7ecampion/problems/2/64/microvirus.htm (hint : construiti automatul de potrivire pentru stringul dat)
* Timus 1158: "Censored!":http://acm.timus.ru/problem.aspx?space=1&num=1158

3698