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)

full code