Dato 2 stringhe s1 e s2, se eseguo un semplice controllo di uguaglianza, è considerato come O (n) quando si calcola l'efficienza dell'algoritmo. Quindi, se sto usando un approccio a forza bruta per substring ruotato domanda l'efficienza è O (n ^ 2) (prendi la seconda sottostringa, ruota di 1 e verifica.Ripeti fino a rotazioni = strlen o abbinata)
Tuttavia, una ricerca del dizionario è considerata O (1). Se invece usassi un dizionario con il solo elemento avente un valore fittizio e una chiave = s1. Quindi, invece di fare una comparazione di stringhe ho verificato l'esistenza di s2 nel dizionario, la mia complessità non sarebbe andata a O (n)?
Intuitivamente non ha senso per me, quindi suppongo che una delle mie supposizioni sia errata ...