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?