raashidanwar's blog

By raashidanwar, 4 years ago, In English

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

  • Vote: I like it
  • +30
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much for writing this :D

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Or we can just use Suffix Automaton.

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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing, thank you very much!

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

There is a pretty straight-forward $$$O(n \log n)$$$ solution without any hashes or suffix structures:

s = input()
n = len(s)
pos = [i for i in range(n)]
for i in range(n):
    c = min(s[(it + i) % n] for it in pos)
    pos = [it for it in pos if s[(it + i) % n] == c]
    pos = [pos[j] for j in range(len(pos)) if j == 0 or pos[j] - pos[j - 1] != i + 1]
print(s[pos[0]:] + s[:pos[0]])

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$$$.