title: Determine how many rotations of a string match the original string in O(n) time?
body: <p>There are lots of questions discussing the fastest/best way to rotate a string or determine if one string is a rotation of another.</p>
  
  <p>For example, neglecting sanitization of inputs, you'll see <a href="https://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string">something like this</a> for IsRotation:</p>
  
  <pre><code>public static bool IsRotation(string s1, string s2)
  {
      return (s1.Length == s2.Length &amp;&amp; (s1 + s1).IndexOf(s2) != -1);
  }
  </code></pre>
  
  <p>And something like this for Rotate:</p>
  
  <pre><code>public static string Rotate(string s, int index)
  {
      //Can't rotate.  Return input.
      if (s.Length &lt; 2)
      {
          return s;
      }
  
      // Break input in half at rotation index
      var s1 = s.Substring(0, index);
      var s2 = s.Substring(index);
  
      // Reverse the halves
      var s1Reversed = Reverse(s1);
      var s2Reversed = Reverse(s2);
  
      // Join the reversed halves
      var joined = s1Reversed + s2Reversed;
  
      //Reverse and return the result.
      var rotated = Reverse(joined);
      return rotated;
  }
  </code></pre>
  
  <p>For example, using "foo..."
  Rotate("foo",1) == "ofo"
  -and-
  IsRotation("foo", "ofo") == true;</p>
  
  <p>My question is is an extension of these questions.</p>
  
  <p>Given an input string, s, determine how many rotations of that string are identical to the original string.</p>
  
  <p>Considering the input string as a rotation, some sample input/output pairs:</p>
  
  <pre><code>IdenticalRotationCount("") == 1
  IdenticalRotationCount("s") == 1
  IdenticalRotationCount("sa") == 1
  IdenticalRotationCount("ss") == 2
  IdenticalRotationCount("ByeBye") == 2
  IdenticalRotationCount("StackOverflow") == 0
  </code></pre>
  
  <p>I was told that there is a solution that will run in O(n) time.  The beginner solution looks like this:</p>
  
  <pre><code>public static int IdenticalRotationCount(this string s)
  {
      //If length of s is less than two, we cannot rotate.  Return 1.
      if (s.Length &lt; 2)
      {
          return 1;
      }
  
      //Get first char in s
      var first = s[0];
  
      //Consider input as first rotation that matches
      var count = 1;
  
      //Try each rotate position
      for (var i = 1; i &lt; s.Length; ++i)
      {
          var c = s[i];
  
          //If current character doesn't start with same character as input
          //we can skip the rotation
          if (c != first)
          {
              continue;
          }
  
          //If the rotation at index i equals the input string, add 1 to result
          if (StringExtensions.Rotate(s, i) == s)
          {
              ++count;
          }
      }
  
      return count;
  }
  </code></pre>
  
  <p>However, if you choose an absurd input, like 200,000 consecutive 'a's, it will run for quite some time.</p>
  
  <p>Can anybody provide a solution that runs in O(n) time?  I can see N^2 by doing the actual comparison when breaking the input down into the two halves before rotation, instead of doing the actual rotation, but cannot see how to do O(n).</p>
  
  <p>Thanks!</p>
  
  <p>PS - If there is a more appropriate to post this sort of question, please say so in the comments.  I'll gladly move it.</p>