Hello, codeforces.
I think this technique is important, and easy to code, although I haven't found much about it, so I've decided to make a blog explaining it.This technique allows to compare substrings lexicographically in O (1) with a preprocessing in O (NlogN).
As this is my first post on codeforces, please let me know if there are any mistakes.
Prerequisites:
- Basic strings knowledge.
- Sparse Table(Optional).
What Dictionary of Basic Factors is?
As in the sparse table we will have a matrix of size $$$NlogN$$$ called $$$DFB$$$, where $$$DFB[i][j]$$$ tells us the position of the string $$$S[i ... i + 2^j-1]$$$ among all the strings of size $$$2^j$$$ ordered lexicographically.
So, how do we build the matrix? Let's start with the lowest level, for powers of size $$$2^0$$$, we simply put the position of the character $$$S[i]$$$ in the dictionary (1 for A, 2 for B ... and so on).
For the following $$$ DFB[i][j] $$$ we can save a pair of numbers that are $$$ (DFB[i][j-1], DFB[i+2^{j-1}][j-1]) $$$
