c# - 如何概括我的算法以检测一个字符串是否是另一个字符串的旋转

Question

因此，我一直在研究各种问题来复习即将到来的面试，我遇到的一个问题是确定两个字符串是否是彼此的旋转。显然，我不是第一个解决这个问题的人。事实上，我确实发现我解决这个问题的想法似乎与 this question 中采用的方法相似。 .

完全披露:我确实有一个 related question在 Math SE 上，它从更数学的角度关注属性(尽管值得注意的是，由于那里解释的原因，我试图阐明其背后的想法的方式最终是不正确的)。

想法是这样的(这类似于链接问题中采用的方法):假​​设您有一个字符串 abcd和旋转 cdab .显然，cd和 ab是 cdab 的子串, 但如果你将它们连接在一起，你会得到 abcd .

所以基本上，旋转只是需要将子字符串从字符串的末尾移动到开头(例如，我们通过将 cdab 从字符串的末尾移动到字符串的开头，从 abcd 构造 cd ).

我想出了一种在非常有限的情况下有效的方法(如果两个子字符串都由连续的字母组成，就像它们在示例中所做的那样)，但否则它会失败(我给出了一个通过和失败的例子代码下方的案例和输入/输出)。我试图弄清楚是否有可能(或什至值得)尝试修复它以在一般情况下工作。

    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<int> distinctRotationLengths = new List<int>();
        for (int i = 0; i < 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;
    }

现在是示例输入/输出:

        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");

是否有可能/值得挽救这种方法并让它仍然是 O(n)，或者我应该只采用我链接到的帖子中描述的一种方法？ (请注意，这实际上不是生产代码或家庭作业，它纯粹是为了我自己的学习)。

编辑:为了根据评论进一步澄清，这里实际上有两个问题 - 第一，这个算法是否可以修复？其次，修复它是否值得(或者我应该尝试另一种方法，如答案中描述的方法或我链接到的其他问题)？我想到了一些可能的修复方法，但它们都涉及到不雅的特例推理或使该算法成为 O(n^2)，这两者都会首先扼杀算法的意义。

Answer 1

假设第一个字符串是 S，第二个是 S'，很明显，如果它们的长度不同，那么我们输出的不是彼此的旋转。创建一个字符串 S''=SS。实际上是 S 到自身的连接。然后如果 S,S' 是彼此的旋转，我们通过 KMP 在 S'' 中找到一个子串 S'算法在O(n)，否则我们输出它们不是彼此的旋转。顺便说一句，如果您正在寻找一种快速实用的算法，那么请使用 Boyer Moore 算法代替 KMP。

为了更明确地解决这个问题，我想说我不希望有一个简单的算法来解决这种特殊的字符串匹配问题。所以考虑到这个背景，我认为对你的算法进行简单的修改是行不通的。事实上，字符串匹配算法领域非常发达。如果有比 KMP 或基于后缀树的算法更简单的算法，对于这种特殊情况，那么我仍然认为研究那些通用算法会有帮助。