Salve a tutti.
problema: dato l'algoritmo di string matching naive.
codice:
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?