Pagini recente » Atasamentele paginii Sg1 | Diferente pentru automate-finite-si-kmp intre reviziile 44 si 29 | Atasamentele paginii Exp | Diferente pentru problema/maxsubsum intre reviziile 7 si 8 | Diferente pentru automate-finite-si-kmp intre reviziile 19 si 20
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 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.
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$}.
h3. Algoritm_calcul_functie_prefix
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
