如何推广我的算法以检测一个字符串是否是另一个字符串的旋转

Question

因此,我一直在审查各种问题,以便对即将进行的访谈进行审核,我遇到的一个问题是确定两个字符串是否相互轮换.显然,我不是第一个解决这个问题的人.事实上,我确实发现我解决这个问题的想法与这个问题中采用的方法类似.

完全披露:我确实有一个关于数学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),否则我们输出它们不是彼此的旋转.顺便说一句,如果你正在寻找一个快速实用的算法,那么代替KMP使用Boyer Moore算法.

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