performance - Determine how many rotations of a string match the original string in O(n) time? -

there lots of questions discussing fastest/best way rotate string or determine if 1 string rotation of another.

for example, neglecting sanitization of inputs, you'll see something this isrotation:

public static bool isrotation(string s1, string s2) {     return (s1.length == s2.length && (s1 + s1).indexof(s2) != -1); } 

and rotate:

public static string rotate(string s, int index) {     //can't rotate.  return input.     if (s.length < 2)     {         return s;     }      // break input in half @ rotation index     var s1 = s.substring(0, index);     var s2 = s.substring(index);      // reverse halves     var s1reversed = reverse(s1);     var s2reversed = reverse(s2);      // join reversed halves     var joined = s1reversed + s2reversed;      //reverse , return result.     var rotated = reverse(joined);     return rotated; } 

for example, using "foo..." rotate("foo",1) == "ofo" -and- isrotation("foo", "ofo") == true;

my question is extension of these questions.

given input string, s, determine how many rotations of string identical original string.

considering input string rotation, sample input/output pairs:

identicalrotationcount("") == 1 identicalrotationcount("s") == 1 identicalrotationcount("sa") == 1 identicalrotationcount("ss") == 2 identicalrotationcount("byebye") == 2 identicalrotationcount("stackoverflow") == 0 

i told there solution run in o(n) time. beginner solution looks this:

public static int identicalrotationcount(this string s) {     //if length of s less two, cannot rotate.  return 1.     if (s.length < 2)     {         return 1;     }      //get first char in s     var first = s[0];      //consider input first rotation matches     var count = 1;      //try each rotate position     (var = 1; < s.length; ++i)     {         var c = s[i];          //if current character doesn't start same character input         //we can skip rotation         if (c != first)         {             continue;         }          //if rotation @ index equals input string, add 1 result         if (stringextensions.rotate(s, i) == s)         {             ++count;         }     }      return count; } 

however, if choose absurd input, 200,000 consecutive 'a's, run quite time.

can provide solution runs in o(n) time? can see n^2 doing actual comparison when breaking input down 2 halves before rotation, instead of doing actual rotation, cannot see how o(n).

thanks!

ps - if there more appropriate post sort of question, please in comments. i'll gladly move it.

this sprung mind - think question "if concatenate original string itself, what's first index of original string within concatenated result". little thought, looks me though it'll answer question o(n).

e.g. original string "byebye" concatenated string "byebyebyebye"

original string appears @ (0-based) index 2 within concatenated string. tells something.