BubbleRing

I have read the task few times but stil don't get what I have to do. Here is my idea:

# include <iostream>
using namespace std;


string Ring, patt;

int main(){
    
    int con, poz;
    string sol = "A";
    
    cin >> Ring;
    for( int i=0; i < Ring.length(); i++ ){
        
         patt = Ring.substr( i, Ring.length() - i );
         patt = patt + Ring.substr( 0, i );
         
         if( patt > sol ){
             sol = patt;
             con = 1;
             poz = i+1;
         }
         
         if( patt == sol )con++;
    }
    
    cout << con << " " << poz << endl;
    return 0;
}

I extracted every circle substring and compared them, and just output the result.
But its obviously wrong. The sample test gives the correct result, but it fails on every test-case. thx in advance

after the input let Ring = Ring + Ring, so you don't have troubles with parts and then just take first length from string and just compare, I had the same idea but it fails on time on some of them , I think it fails cuz there are some huge strings that are equal so comparing takes time, can someone who solved this task tell if the solution is based on using HASHS?

Yeah, you were right. I had a silly bug, but as you said it fails on time( on 3 test-cases )

I'm sure that this task is to be solved with suffix array, but I can't implement it to run under 0.1 sec...

hmm, i've solved the problem, and i tried many approaches, but the one that worked for me was of linear complexity. the idea was to find the maximum rotation of the string ( in O( N ) ), and then count the number of those in the concatenation of the string to itself..
And yes, some people solved it using hashing.

What do you mean by maximum rotation of a string?

the lexicographically largest rotation of the word you get from the input. it can be found in O( N ) time complexity.

How, can you explain a little more what were you doing ?

okay... so let's say the first rotation ( one starting from position 0 ) is the current maximum candidate. we start comparing it to the other rotations ( ones starting at 1, and so on ). we keep track of the current maximal rotation, the next rotation we're comparing it to, and the length of the segment we've compared so far. ( let's call those values m ( maximum ), c ( current ), and l ( length ) ). if we have a match at the position we're checking ( ( c + l )%N, m + l ), we can increase l by one. if the character of the maximum candidate is larger than the character of the current rotation, the maximum remains the same, but we move the position we're checking further. we see there are no interesting rotations between c and c + l inclusive, so we can set c to c + l + 1, and l to 0 ( we haven't matched anything there yet ).
if the current character of the maximal candidate we're looking at is smaller then the one we're matching it to, we have to change it... the first guess is the rotation we were matching it to ( c ), but the next character of the last maximal candidate could be positioned further to the right of it, so m becomes max( c, m + l + 1 ), c becomes m+1, and l again becomes 0. we do this while c is less than N, and the m + l + 1 is less than N. as at least one of the values changes through the process, the algorithm runs in linear complexity... now, after you've found the maximal rotation, you can count the number of its occurrences using a string matching algorithm ( Boyer-Moore, KMP, or any other you find easiest to implement ) .