== code(c) |
n <- lungime(N)
k <- 0

&#960;[1] <- 0

pi[1] <- 0

pt i <- 2, n
    cat timp (k > 0) si (N[k + 1] ** N[i])

        k <- &#960;[k]

        k <- pi[k]

    daca N[k + 1] = N[i]
        k <- k + 1

    &#960;[i] <- k

    pi[i] <- k

==

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

* 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

=> Complexitate : O(n)

=> Complexitate : $O(n)$

Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare i in care s-a acceptat Ni, vedem cat de mult putem lua de la sfarsitul lui Ni 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 p[k]. Aceasta este de fapt "magia" care ofera complexitate liniara.

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 {$Π{~k~}$}. Aceasta este de fapt "magia" care ofera complexitate liniara.

Algoritmul de potrivire este similar celui al calculului functiei prefix, numai ca aici la fiecare pas i cautam cel mai lung prefix al lui N care este sufix al lui Mi.

Algoritmul de potrivire este similar celui al calculului functiei prefix, numai ca aici la fiecare pas $i$ cautam cel mai lung prefix al lui $N$ care este sufix al lui {$M{~i~}$}.

h3. Algoritm_potrivire_KMP

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])
5: q <- pi[q]
6: daca N[q + 1] = M[i]
7: q <- q + 1
8: daca q = n
9: scrie "potrivire la pozitia " i - n + 1
 
 
 
Analog Algoritm_Calcul_Functie_Prefix, complexitatea algoritmului efectiv de potrivire este O(m). Astfel rezulta complexitatea liniara a algoritmului KMP O(n + m)
 
Teme pentru acasa:
 
- folosind functia prefix, rafinati constructia automatului finit de acceptare pt un string, aducand-o la complexitatea O(m^2 * |S|)
- problema "[1]Microvirus" (hint : construiti automatul de potrivire pentru stringul dat)
- Timus 1158
 

== code(c) |
m <- lungime(M), n <- lungime(N)
q <- 0
pt i <- 1, m
    cat timp (q > 0) si (N[q + 1] != M[i])
        q <- pi[q]
    daca N[q + 1] = M[i]
        q <- q + 1
    daca q = n
        scrie "potrivire la pozitia " i - n + 1
==
Analog Algoritm_Calcul_Functie_Prefix, complexitatea algoritmului efectiv de potrivire este {$O(m)$}. Astfel rezulta complexitatea liniara a algoritmului KMP $O(n + m)$

References

h2. Teme pentru acasa:

Visible links
1. http://www.liis.ro/%7ecampion/problems/2/64/microvirus.htm

* folosind functia prefix, rafinati constructia automatului finit de acceptare pt 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