如何找到从 s1 到 s2 的最小可能循环移位？

Question

如果我有 2 个字符串s1和s2，其中s2是循环移位的字符串s1。s1它需要找到从到的最小可能循环偏移s2。

让我举个例子：

s1 = 'I love cookies '

s2 = 'cookies I love ' 答案是7。

最好采用线性时间。有我失败的试验：

def find_minimum_cyclic_shift(s1, s2):

        if len(s1) != len(s2):

            return -1

        index = s2.index(s1[0])

        if (index > -1):

            if (s1==s2):

                return 0;

            #finalPosition = len(s2) - index

            #print(finalPosition, " index=",index)

            #return s2[0] == s1[finalPosition] and s1[finalPosition::]==s2[0:index]

        return index

但它不适用于 case: absabsabsfand absfabsabs。而不是 4 我有 0. 因为索引函数只返回我第一次出现的字母。

请至少给我一个逻辑来编码它。

Answer 1

find您可以简单地在双字符串上使用，如下所示：s1 = 'I love cookies 's2 = 'cookies I love 'answer = min((s1*2).find(s2), (s2*2).find(s1))print(answer)输出：7-1（如果s2不是 的循环移位，将打印s1）。它起作用的原因是如果s2确实是 的循环移位s1，那么连接s1到自身将包含s2中间的某个地方。s1幸运的是，这个“某处”正好是所需移位的大小（出现在s2第一个字符之前的字符数）。我们还需要检查“其他方向”以获得可能更短的移位，因此我们从两个可能的方向获取最小结果（技术上可以使用算术来避免第二次搜索，如果结果是那么答案很简单 -> n/2结果n。关于运行时复杂性的注意事项：我的解决方案不保证线性时间，基于这个答案，它可以O(N*N)在最坏的情况下使用。