performance - 在 O(n) 时间内确定字符串与原始字符串匹配的旋转次数？

Question

有很多问题都在讨论旋转字符串或确定一个字符串是否是另一个字符串的旋转的最快/最佳方法。

例如，忽略输入的清理，您会看到 something like this对于 IsRotation:

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

像这样的旋转:

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;
}

例如，使用“foo...”旋转(“foo”，1)==“ofo”-和-IsRotation("foo", "ofo") == true;

我的问题是这些问题的延伸。

给定一个输入字符串 s，确定该字符串的旋转次数与原始字符串相同。

将输入字符串视为旋转，一些示例输入/输出对:

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

有人告诉我有一个解决方案可以在 O(n) 时间内运行。初学者解决方案如下所示:

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;
}

但是，如果您选择一个荒谬的输入，例如 200,000 个连续的 'a'，它会运行相当长的一段时间。

谁能提供一个在 O(n) 时间内运行的解决方案？在旋转之前将输入分解为两半时，我可以通过实际比较看到 N^2，而不是进行实际旋转，但看不到如何做 O(n)。

谢谢!

PS - 如果有更适合发布此类问题的信息，请在评论中说明。我很乐意移动它。

Answer 1

这突然出现在脑海中 - 想想这个问题“如果我将原始字符串与其自身连接起来，连接结果中原始字符串的第一个索引是什么”。稍加思索，在我看来它似乎可以回答 O(n) 问题。

例如原始字符串“ByeBye”连接字符串“ByeByeByeBye”

原始字符串出现在连接字符串中的(从 0 开始)索引 2 处。这告诉你一些事情。