abcyyyy's blog

How to solve this problem ,
By abcyyyy, history, 6 years ago, In English

How to solve a question where the string is first circularly rotated by 1 letter, then by 2 letter and soon , at what time the modified string will be equal to original string? these strings are made up using 'a' and 'b' only.

for eg: aabaab is the string on first letter rotation it will become abaaba on second rotation it will become aabaab so answer is 2.

I tried to solve this question but could only do this only by brute force. https://pasteboard.co/Hz1WUBx.jpg

Any help will be appreciated.

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Use prefix or z function, or suffix array, or hashes.

http://e-maxx.ru/algo/prefix_function

http://e-maxx.ru/algo/z_function

http://e-maxx.ru/algo/string_hashes

http://e-maxx.ru/algo/suffix_array

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

To explain what is exactly asked from us; suppose the maximum number of strings that can be equal each one to their original selves at any certain time(let it be t) is x.Of course, there will be a time when they will all be equal to their original selves again.We just need to print the first time that this happens.

For a string s of length n, let nb be the minimum number of characters such that s will be equal to s rotated by nb letters.We can find it in O(n2) like this:

for(int i=1;i <= s.size();++i){
    string x(s.begin(),s.begin()+i);
    string y(s.begin()+i,s.end());

    string xx = x+y;
    string yy = y+x;

    if(xx == yy){
        cout << i;
        break;
    }
}

But that's too much since the n <  = 105.

Turns out, nb is the length of the period of s !

A period of a string s is the smallest string m such that there exists an integer k > 0 where s = m+m+m+m+... (k times).

For s = "abaa" , nb = 4 and for s = "aabaab" , nb = 3.

This can be computed with the KMP algorithm in O(n).

Now that we calculated the length of the periods of all the strings, comes the second part of the problem.For a string s of length n, let it's period's length be nb.We need to find the minimum time t such that the number of letters moved from time 1 to t(in total) is a multiple of nb.

For a string of length n, the total number of letters moved at a time t is equal to:

t/n * (n*(n+1))/2 + t%n * (t*(t+1))/2.

We need to find for every string s, the couple (t, k) such that s is back to it's original self at times t, t+k, t+2*k... (k has to be minimum).

Then using these couples for all the strings, we need to find the maximum number of strings such that their times(the ones t+k, t+2*k ...) intersect and return the minimum instant of time that these strings intersect at.Don't forget the modulo 109 + 7 !

Honestly, I still haven't completely figured out how to find these couples nor how to do the last part in O(n).

Perhaps someone else can help?

→ Reply