title: How to generalize my algorithm to detect if one string is a rotation of another
body: <p>So I've been going through various problems to review for upcoming interviews and one I encountered is determining whether two strings are rotations of each other. Obviously, I'm hardly the first person to solve this problem. In fact, I did discover that my idea for solving this seems similar to the approach taken in <a href="https://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string">this question</a>.</p>
  
  <p>Full disclosure: I do have a <a href="https://math.stackexchange.com/questions/2075186/beginner-question-algebraic-properties-of-string-rotations">related question</a> on Math SE that's focused on the properties from a more mathematical perspective (although it's worth noting that the way that I tried to formulate the ideas behind this there end up being incorrect for reasons that are explained there).</p>
  
  <p>Here's the idea (and this is similar to the approach taken in the linked question): suppose you have a string <code>abcd</code> and the rotation <code>cdab</code>. Clearly, both <code>cd</code> and <code>ab</code> are substrings of <code>cdab</code>, but if you concatenate them together you get <code>abcd</code>.</p>
  
  <p>So basically, a rotation simply entails moving a substring from the end of the string to the beginning (e.g. we constructed <code>cdab</code> from <code>abcd</code> by moving <code>cd</code> from the end of the string to the beginning of the string).</p>
  
  <p>I came up with an approach that works in a very restricted case (if both of the substrings consist of consecutive letters, like they do in the example there), but it fails otherwise (and I give an example of passing and failing cases and inputs/outputs below the code). I'm trying to figure out if it's possible (or even worthwhile) to try to fix it to work in the general case.</p>
  
  <pre><code>    public bool AreRotations(string a, string b)
      {
          if (a == null)
              throw new ArgumentNullException("a");
          else if (b == null)
              throw new ArgumentNullException("b");
          else if (a.Trim().Length == 0)
              throw new ArgumentException("a is empty or consists only of whitespace");
          else if (b.Trim().Length == 0)
              throw new ArgumentException("b is empty or consists only of whitespace");
  
          // Obviously, if the strings are of different lengths, they can't possibly be rotations of each other
          if (a.Length != b.Length)
              return false;
  
          int[] rotationLengths = new int[a.Length];
  
          /* For rotations of length -2, -2, -2, 2, 2, 2, the distinct rotation lengths are -2, 2
           * 
           * In the example I give below of a non-working input, this contains -16, -23, 16, 23
           * 
           * On the face of it, that would seem like a useful pattern, but it seems like this
           * could quickly get out of hand as I discover more edge cases
           */
          List&lt;int&gt; distinctRotationLengths = new List&lt;int&gt;();
          for (int i = 0; i &lt; a.Length; i++)
          {
              rotationLengths[i] = a[i] - b[i];
  
              if (i == 0)
                  distinctRotationLengths.Add(rotationLengths[0]);
              else if (rotationLengths[i] != rotationLengths[i - 1])
              {
                  distinctRotationLengths.Add(rotationLengths[i]);
              }
          }
  
          return distinctRotationLengths.Count == 2;
      }
  </code></pre>
  
  <p>And now for the sample inputs/outputs:</p>
  
  <pre><code>        StringIsRotation rot = new StringIsRotation();
  
          // This is the case that doesn't work right - it gives "false" instead of "true"
          bool success = rot.AreRotations("acqz", "qzac");
  
          // True
          success = rot.AreRotations("abcdef", "cdefab");
  
          // True
          success = rot.AreRotations("ablm", "lmab");
  
          // False, but should be true - this is another illustration of the bug
          success = rot.AreRotations("baby", "byba");
  
          // True
          success = rot.AreRotations("abcdef", "defabc");
  
          //True
          success = rot.AreRotations("abcd", "cdab");
  
          // True
          success = rot.AreRotations("abc", "cab");
  
          // False
          success = rot.AreRotations("abcd", "acbd");
  
          // This is an odd situation - right now it returns "false" but you could
          // argue about whether that's correct
          success = rot.AreRotations("abcd", "abcd");
  </code></pre>
  
  <p>Is it possible/worthwhile to salvage this approach and have it still be O(n), or should I just go with one of the approaches described in the post I linked to? (Note that this isn't actually production code or homework, it's purely for my own learning).</p>
  
  <p><strong>Edit:</strong> For further clarification based on the comments, there are actually two questions here - first, is this algorithm fixable? Secondly, is it even <em>worth</em> fixing it (or should I just try another approach like one described in the answers or the other question I linked to)? I thought of a few potential fixes but they all involved either inelegant special-case reasoning or making this algorithm O(n^2), both of which would kill the point of the algorithm in the first place.</p>