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 toget(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
raashidanwar 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
Amazing, thank you very much!
There is a pretty straight-forward $$$O(n \log n)$$$ solution without any hashes or suffix structures:
Yes, this is the whole solution. Explanation:
We maintain a set of indices on which lexicographically minimum shift may start. We obviously remove those of them that are pro-longed by the character which is not minimum possible.
If we do just that, it would be $$$O(n^2)$$$ on strings like $$$aa\dots a$$$. Important observation here is if two shifts touched (for example, $$$[ab][ab]$$$ in $$$dababc$$$), we may remove the second one from the set, as it would never be better then the first one.
Why is it better? We maintain set of non-overlapping shift prefixes. So, on $$$k$$$-th step there are at most $$$\frac{n}{k}$$$ positions in $$$pos$$$. Ergo, the full algo works in $$$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\dots+\frac{n}{n} \sim n \lg n$$$.