Pagini recente » Diferente pentru teorema-chineza-a-resturilor intre reviziile 89 si 18 | Diferente pentru planificare/sedinta-20091023 intre reviziile 50 si 54 | Diferente pentru monthly-2014/runda-9/solutii intre reviziile 3 si 4 | Diferente pentru teorema-chineza-a-resturilor intre reviziile 31 si 30 | Diferente pentru automate-finite-si-kmp intre reviziile 32 si 31
Nu exista diferente intre titluri.
Diferente intre continut:
h2. Algoritmul KMP
Gaseste toate aparitiile unui 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 unui 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.
