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

Question

There are lots of questions discussing the fastest/best way to rotate a string or determine if one string is a rotation of another.

For example, neglecting sanitization of inputs, you'll see something like this for IsRotation:

public static bool IsRotation(string s1, string s2)
{
    return (s1.Length == s2.Length && (s1 + s1).IndexOf(s2) != -1);
}

And something like this for Rotate:

public static string Rotate(string s, int index)
{
    //Can't rotate.  Return input.
    if (s.Length < 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;
}

For example, using "foo..." Rotate("foo",1) == "ofo" -and- IsRotation("foo", "ofo") == true;

My question is is an extension of these questions.

Given an input string, s, determine how many rotations of that string are identical to the original string.

Considering the input string as a rotation, some sample input/output pairs:

IdenticalRotationCount("") == 1
IdenticalRotationCount("s") == 1
IdenticalRotationCount("sa") == 1
IdenticalRotationCount("ss") == 2
IdenticalRotationCount("ByeBye") == 2
IdenticalRotationCount("StackOverflow") == 0

I was told that there is a solution that will run in O(n) time. The beginner solution looks like this:

public static int IdenticalRotationCount(this string s)
{
    //If length of s is less than two, we cannot rotate.  Return 1.
    if (s.Length < 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 < 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;
}

However, if you choose an absurd input, like 200,000 consecutive 'a's, it will run for quite some time.

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).

Thanks!

PS - If there is a more appropriate to post this sort of question, please say so in the comments. I'll gladly move it.

shouldn't IdenticalRotationCount("StackOverflow") == 1 ? since each string is a rotation of itself — faisal, May 03 '13 at 00:03
@faisal - Well, not necessarily. But fair enough; I should have specified. — bopapa_1979, May 29 '13 at 19:29

score 0 · Answer 1 · answered May 02 '13 at 23:21

0

This sprung to mind - think about the question "if I concatenate the original string with itself, what's the first index of the original string within the concatenated result". With a little thought, it looks to me as though it'll answer the question O(n).

E.g. Original string "ByeBye" Concatenated string "ByeByeByeBye"

Original string appears at (0-based) index 2 within the concatenated string. This tells you something.

answered May 02 '13 at 23:21

Will A

24,780
5
50
61

Suppose the string were `n` `a`s followed by one `b` (so that every rotation is unique). The `i`th test will fail at position `n-i`, so the total number of character comparisons will be `O(n^2)`. – rici May 02 '13 at 23:28
@rici - true, was underestimating the cost of determining the position of original in concatenated. D'oh. – Will A May 03 '13 at 13:03

score 0 · Answer 2 · answered May 03 '13 at 00:00

If a string is equal to a rotation of itself at offset k and at no smaller offset, then the string must be the repetition of its length k prefix. It will then also be equal to its rotation at all multiples of k, so there will be precisely n/k such rotations, where n is the length of the string. This is pretty easy to prove.

There is indeed an O(n) algorithm for determining the value of k. One way to do it is to use Duval's algorithm for Lyndon factorization (see Wikipedia). That's just a hint; I'll see if I can produce some actual pseudocode if desired.

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

2 Answers2