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

Question

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

举个例子:

s1 = '我喜欢 cookies '

s2 = '我喜欢的 cookies '这里的答案是 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

但它不适用于以下情况:absabsabsf 和 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 to 本身将包含 s2在中间的某个地方。

幸运的是，这个“某处”恰好是所需移位的大小(s1 中出现在 s2 的第一个字符之前的字符数)。

我们还需要检查“其他方向”以获得可能更短的移位，因此我们从两个可能的方向获取最小结果(技术上可以使用算术来避免第二次搜索，如果结果是 > n/2 那么答案就是 n - 结果。

关于运行时复杂性的注意事项:我的解决方案不保证线性时间，基于 this answer , 它可以采取 O(N*N)在最坏的情况下。