it's for beginners.

it's my first blog.

Here i'm discussing about a specific problem Minimal Rotation. how can we use hashing to solve this particular problem in **O(nlog(n))** although we can solve it in **O(n)** using Booth's Algorithm

after understanding this blog you will be able to solve problems based on KMP, Booth's Algorithm, Manacher’s Algorithm without even knowing them but i insist you know those algorithms

**Beauty of Hashing :**

let's consider we have a string **"abcd"** first we need to construct prefix Hash array.

`Hash[i + 1] = s[0] - 'a' + (s[1] - 'a') * 131 +++++++++ (s[i] - 'a') * (131 --- i times --- 131)`

```
const int M1 = 1000000007;
int x = 1;
H[0] = 0;
for(int i = 0; i < n; i++) {
Hash[i + 1] = (Hash[i] + x * (s[i] - 'a')) %M1;
x *= 131;
x %= M1;
}
```

you can see **H[i+1]** as a polynomial function with having coefficients **(s[0]-'a', s[1]-'a', ....., s[i]-'a')** and where we take x = 131

our aim is to **get(l, r) = (s[l]-'a') + (s[l+1]-'a') * 131 +++++ (s[r]-'a') * 131... r — l times ...131** where **l <= r**

we have `get(r) = Hash[r + 1]`

and `get(l - 1) = Hash[l]`

how can we get get(l, r)? yes you are right we are going use get(r) and get(l — 1)

`get(r) - get(l - 1) = (s[l] - 'a') * (131 ... l times ... 131) + (s[l + 1] - 'a') * (131 ... (l + 1) times ... 131) ++++ (s[r] - 'a') * (131 ... r times ... 131)`

if divide it by power(131, l) we `get(l, r) = (s[l]-'a') + (s[l+1]-'a') * 131 +++++ (s[r]-'a') * 131... r - l times ...131`

as we are using `M1 = 1000000007`

so for division purpose we will store inverse power of 131 `p[i] = (1 / (131 ... i times ...)) % M1;`

```
int x = 1;
for(int i = 0; i < n; i++) {
p[i] = mpow(x, M1 - 2);
x *= 131;
x %= M1;
}
```

or

```
p[n - 1] = mpow(mpow(131, n - 1), M1 - 2);
for(int i = n - 2; ~i; i--)
p[i] = (p[i + 1] * 131) % M1;
```

so finally we are here to find **get(l, r)**

**Note** get(l , r) { i am considering string from 1 to n instead of 0 to n — 1 }

```
int get(int l ,int r) {
return ((Hash[r] - Hash[l - 1] + M1) * p[l - 1]) % M1;
}
```

- if
`get(l1, r1)`

is equals to`get(l2, r2)`

it's means both substrings are same ( 1 <= l1 <= r2 <= n and 1 <= l2 <= r2 <= n)

problem Minimal Rotation

first concatenate `s = s + s`

because we know that `s.substr(i, i + n - 1)`

is the i'th rotation of string s it's just for easy understanding. still you can do without concatenation but you must take care of rotation.

take k — 1 as the starting index of our minimal Lexicographically rotation string lets consider k = 1 ( string(0, n) is minimal string)

you must be thinking why not k = 0 as i told you i am taking string with 1 not with 0)

Now for ith rotation, the idea is to find the largest prefix that mathces with the prefix of current answer(starting at index k-1). This can be done using binary search over the largest length l[0,n-1] and check if get(i,i+l) equals get(k,k+l).

now iterate over string `for 2 .... n`

(n is the length of string without concatenation)

and do binary search to find the maximum length l where `s.substr(k - 1, l) is equals s.substr(i - 1, l)`

`if l equals n no further check both are same`

`else check for (l + 1)th character the one with minimum is the the answer for now`

`if s[k - 1 + l] > s[i - 1 + l]]`

`k = i`

`else`

no change

```
s += s;
int k = 1;
int n = s.size() / 2;
for(int i = 2; i <= n; i++) {
int lo = 0, hi = n - 1;
while(lo <= hi) {
int lm = (lo + hi) >> 1;
if(get(i, i + lm) == get(k, k + lm))
lo = lm + 1;
else
hi = lm - 1;
}
if(lo <= n - 1)
if(s[i + lo - 1] < s[k + lo - 1])
k = i;
}
```

**Lexicographically minimal string is** `s.substr(k - 1, n)`

Thank you so much for writing this :D

your welcome

thanks!!

i was using 31 and got WA on one testcase but when i switched to 131 like you i got AC

can u please explain what do u use as a standard when doing rolling hash questions like this?

I always use 131 and sometime 2 hash array one for M1 = 998244353 and other for M2 = 1000000007

Or we can just use Suffix Automaton.

Although the algorithm is hard to learn, it's more universal.

Why am I getting a TLE in this question?My Submission

R.Anwar can you take a look at my submission, please.

you used too many mod (%) operation , no need to use two hash, just do with 1 hash

It worked, thanks