PDA

Visualizza la versione completa : [ALGORITMO] Ottimizzazione di "string matching"


bako
16-10-2007, 17:21
Salve a tutti.
problema: dato l'algoritmo di string matching naive.


NAIVE-STRING-MATCHER(T, P)
1 n ← length[T]
2 m ← length[P]
3 for s ← 0 to n - m
4 do if P[1 m] = T[s + 1 s + m]
5 then print "Pattern occurs with shift"

sapendo che i caratteri del pattern sono tutti diversi, si puņ migliorare arrivando ad avere O(n) dove n č la lunghezza del testo?

pensavo a vedere che se tra i (indice del prima occorenza di P1) e i+m c sia un carattere che si ripete allora skippo fino alla prima occorenza di P1.
ma alla fine viene uguale.
idee?

Loading