### R.Anwar's blog

By R.Anwar, 5 months ago,

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

• +30

 » 5 months ago, # |   0 Thank you so much for writing this :D
•  » » 5 months ago, # ^ |   0 your welcome
 » 3 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   0 I always use 131 and sometime 2 hash array one for M1 = 998244353 and other for M2 = 1000000007
 » 3 months ago, # |   0 Or we can just use Suffix Automaton.Although the algorithm is hard to learn, it's more universal.
 » 5 weeks ago, # | ← Rev. 2 →   0 Why am I getting a TLE in this question?My Submission
•  » » 5 weeks ago, # ^ |   0 R.Anwar can you take a look at my submission, please.
•  » » » 5 weeks ago, # ^ |   0 you used too many mod (%) operation , no need to use two hash, just do with 1 hash
•  » » » » 5 weeks ago, # ^ |   0 It worked, thanks