Se introduci la possibilità di rotazioni, allora in caso di insuccesso potresti ricominciare da qualsiasi ripetizioni delle sotto-stringhe della parte trovata finora.
Supponi per esempio tu abbia "ababf", con "f" sbagliato. A questo punto potresti ripartire da ogni ripetizioni delle stringhe "abab", "bab", "ab" e "b" nella stringa pattern. Mi viene quindi difficile pensare che tu possa mantenere la linearità, sia di tempo che di spazio, della funzione insuccesso e probabilmente andresti anche a moltiplicare per la lunghezza del pattern anche la complessità della funzione di match.
Se questo è vero e non solo una mia impressione, allora sarebbe più performante un approccio del tipo (scritto in uno pseudocodice a caso):
- Codice:
insucc = insuccesso(pat)
for i in [0, len(pat)] :
matched_index = match(stringa, insucc)
if( matched_index != len(string) ) return matched_index;
aggiorna_insuccesso( insucc, pat)
end for
dove aggiorna_insuccesso è una funzione che aggiorna l'array insuccesso per una rotazione verso sinistra.