1

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

例如，忽略输入的清理，您会在 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..." Rotate("foo",1) == "ofo" -and- 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 - 如果有更合适的发布此类问题，请在评论中说出来。我很乐意移动它。

4

2 回答 2

0

如果一个字符串等于它自身在 offset 处的旋转k并且在不小的 offset 处，则该字符串必须是其长度k前缀的重复。然后它也将等于它在 的所有倍数处的旋转k，因此将精确地存在n/k这样的旋转，其中n是字符串的长度。这很容易证明。

确实有一种O(n)算法可以确定 的值k。一种方法是使用 Duval 的 Lyndon 分解算法（参见Wikipedia）。这只是一个提示；如果需要，我会看看是否可以生成一些实际的伪代码。

于 2013-05-03T00:00:06.740 回答
0

这让我想起了这个问题——想想“如果我将原始字符串与自身连接，连接结果中原始字符串的第一个索引是什么”。稍微想一想，在我看来，它好像会回答 O(n) 的问题。

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

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

于 2013-05-02T23:21:18.090 回答