I remember having my mind blown studying the Ukkonen algorithm, for string search prefix trees. Especially the fact that was built from the naïve implementation

I remember having my mind blown studying the Ukkonen algorithm, for string search prefix trees. Especially the fact that was built from the naïve implementation O(N^3) brought down to O(N)