Diferente pentru automate-finite-si-kmp intre reviziile #44 si #33

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Automate finite si KMP
(Categoria _Algoritmi_, Autor _Adrian Vladu_)
(Categoria _Automate_, autor(i) _Vladu Adrian_)
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 ;)
h3. Ce sunt automatele finite ?
Un automat finit este definit ca un cvintuplu {@<@}{$Q, q{~0~}, A, &#0931;, &#0948;$}{@>@} unde $Q$ este o multime finita de stari {$Q = {q{~0~}, q{~1~}, ... q{~n~}}$}, $q{~0~}$ apartine $Q$ ({$q{~0~}$} = stare initiala), $A$ inclus in $Q$ ({$A$} = multimea starilor de acceptare), $&#0931;$ este un alfabet, iar functia {$&#0948; : Q x &#0931; -> Q$} este functia de tranzitie a automatului.
Un automat finit este definit ca un cvintuplu {@<@}{$Q, q{~0~}, A, &#0931;, &#0948;$}{@>@} unde $Q$ este o multime finita de stari {$Q = {q{~0~}, q{~1~}, ... q{~n~}}$}, $q{~0~}$ apartine $Q$ ({$q{~0~}$} = stare initiala), $A$ inclus in $Q$ ({$A$} = multimea starilor de acceptare), $&#0931;$ este un alfabet, iar functia {$&#0948; : Q x S -> Q$}.
Aceasta este definitia matematica si foarte abstractizata a automatelor. Pentru a le intelege mai usor, sa luam un exemplu concret
* $k = 2; &#0948;(2, b) = 0;$
* $k = 0; &#0948;(0, a) = 1;$
* $k = 1; &#0948;(1, b) = 1;$
* $k = 1; &#0948;(1, a) = 3;$
* $k = 2; &#0948;(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 $&#0948;( ... &#0948;( &#0948;(0, s{~1~}), s{~2~} ) ..., s{~n~} )$ apartine {$A$}.
Stringurile '{$aa$}', '{$aaaaaaa$}', '{$aabababab$}', '{$aaaba$}', '{$ba$}', '{$aba$}' sunt acceptate de automat, dar '{$abbbbbb$}', '{$bba$}' nu.
Stringurile '{$aa$}', '{$aaaaaaa$}', '{$aabababab$}', '{$aaaba$}', '{$ba$}', '{$aba$}' sunt acceptate de automat, dar '{$ba$}', '{$abbbbbb$}', '{$bba$}' nu.
h3. La ce folosesc ?
== code(c) |
n = lungime(N)
m = lungime(M)
q = 0;
pt i <- 1, m
pt i <- 1, n
    q = d(q, M[i])
    daca q apartine A
        scrie "potrivire la pozitia " i - n + 1
k <- 0
pi[1] <- 0
pt i <- 2, n
    cat timp (k > 0) si (N[k + 1] != N[i])
    cat timp (k > 0) si (N[k + 1] ** N[i])
        k <- pi[k]
    daca N[k + 1] = N[i]
        k <- k + 1
* 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
* {=>} Complexitate : $O(n)$
* => Complexitate : $O(n)$
Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare $i$ in care s-a acceptat {$N{~i~}$}, vedem cat de mult putem lua de la sfarsitul lui {$N{~i~}$} astfel incat sufixul respectiv sa fie prefix pentru {$N$}. De remarcat ca in cazul in care starea candidata $k$ nu este buna, nu mergem in {$k - 1$}, ci in {$&pi;{~k~}$}. Aceasta este de fapt "magia" care ofera complexitate liniara.
h2. Teme pentru acasa:
* folosind functia prefix, rafinati constructia automatului finit de acceptare pentru un string, aducand-o la complexitatea $O(m^2^ * |&#0931;|)$
* folosind functia prefix, rafinati constructia automatului finit de acceptare pt un string, aducand-o la complexitatea $O(m^2^ * |&#0931;|)$
* 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

Nu exista diferente intre securitate.

Diferente intre topic forum:

3698