如何找到从 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)在最坏的情况下使用。