Nu aveti permisiuni pentru a descarca fisierul grader_test9.in
Diferente pentru automate-finite-si-kmp intre reviziile #20 si #19
Nu exista diferente intre titluri.
Diferente intre continut:
h2. Algoritmul KMP
Gaseste toate aparitiile un string$N$in$M$in timp{$O(n + m)$}, unde{$n = lungime(N)$},{$m = lungime(M)$}. O parte esentiala a sa este functia prefix$Π: {1..n} -> {0..n-1}$unde$Π{~i~}$= cel mai lung prefix al lui$M$care este sufix al lui{$M{~i~}$}. Evident, M{~Π{~i~}~}(prefixul de lungimeΠ{~i~}al lui{$M$}) prefix al lui{$M{~i~}$}, deci{$Π{~i~}< i$}.
Gaseste toate aparitiile un string N in M in timp O(n + m), unde n = lungime(N), m = lungime(M). O parte esentiala a sa este functia prefix p : {1..n} -> {0..n-1} unde p[i] = cel mai lung prefix al lui M care este sufix al lui Mi. Evident, Mp[i] (prefixul de lungime p[i] al lui M) prefix al lui Mi, deci p[i] < i.
h3. Algoritm_calcul_functie_prefix
