"Rotating the string" optimization

Below is the code for the problem at Codechef. I have made use of the String method .equals in my solution which is working fine for all the test inputs. However, I am getting a Time Limit Exceeded when I submit to the Judge. I need your ideas on optimizing the code.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{

    public static void main(String args[]) throws IOException
    {

        BufferedReader in =new BufferedReader(new InputStreamReader(System.in));

        int not=Integer.parseInt(in.readLine());

        for(int i=0;i0)
                System.out.println(count);
            else
                System.out.println(-1);

        }

    }   private static String rotate(int m, String s) {

        char sa[]=s.toCharArray();

        int l=sa.length;

        StringBuilder sb=new StringBuilder();

        for(int j=m-1;j>=0;j--)
        {

            sb.append(sa[l-1-j]);

        }

        for(int k=0;k<(l-m);k++)
            sb.append(sa[k]);

        return sb.toString();
    }

}

I would use an entirely different strategy to determine the number of times needed to rotate the string: addition.

Since rotating a string by a and then b yields the same result as rotating it a+b, we do not need to keep track of the string at all, only the equivalent rotation. However, we do need to be able to detect if the string is actually just concantenations of some substring; in that case we can treat it as if its length were the length of the repeated substring.

Here are the steps I would use for each string:

-
Match the string against the regular expression (.+?)\1+. This uses a backreference to find the iterated portions of the string. (FYI, this regex may need some adjustment.)

static final Pattern iteratedSubstring = Pattern.compile("(.+?)\\1+");
static int reducedLength(String string){
    Matcher m = iteratedSubstring.matcher();
    if(m.matches(input)) return m.group(1).length()

    return string.length()
}

-
Repeatedly accumulate the two rotations until the rotation is congruent to zero modulo the length.

static int identityRotationCount(final int length, int ... rotations){
    rotations = Arrays.stream(rotations).parallel().flatMap(i->i%length).toArray();

    /* alternately, if you can't use java 8 you can do this, although it's slower:
    for(int idx = 0; idx  length) rotation -= length;
        }
}

There may be even faster methods to compute this, including variants on algorithms for finding a GCD or other discrete algebra type things.

-
At least at first, you should be using a Scanner to process the input, because inevitable parsing logic bugs from doing the parsing yourself will make debugging anything else extremely difficult.

try(Scanner in = new Scanner(System.in), PrintWriter out = System.out){
    // ...
}

-
Finish the program:

in.nextInt(); //discard input entry count, don't need it.

while(true){
    if(!in.hasNextLine()) break;
    String string = in.nextLine();

    if(!in.hasNextInt()) break;
    int monkey = in.nextInt();

    if(!in.hasNextInt()) break;
    int po = in.nextInt();

    out.println(identityRotationCount(reducedLength(string), monkey, po));
}

-
If you do not want to use a Scanner, try something like this:

try(BufferedReader in = new BufferedReader(System.in), PrintWriter out = System.out){
    int n = Integer.parseInt(in.readLine());

    for(int idx = 0; idx < n; idx++){
        String string = in.readLine();

        String [] rots = in.readLine().split("\\s");

        int monkey = Integer.parseInt(rots[0]),
                  po = Integer.parseInt(rots[1]);

        out.println(identityRotationCount(reducedLength(string), monkey, po));
    }
}

StackExchange Code Review Q#48323, answer score: 5