如何找到从 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

但它不适用于以下情况：absabsabsf 和 absfabsabs。而不是 4 我有 0。因为索引函数 returns 我只是第一个出现的字母。

拜托，至少给我一个编码的逻辑。

Answer 1

您可以简单地在双字符串上使用 find，如下所示：

s1 = 'I love cookies '
s2 = 'cookies I love '

answer = min((s1*2).find(s2), (s2*2).find(s1))
print(answer)

输出：

（如果 s2 不是 s1 的循环移位，将打印 -1）。

它起作用的原因是，如果 s2 确实是 s1 的循环移位，那么将 s1 连接到自身将在中间某处包含 s2。

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

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

关于运行时复杂性的注意事项：我的解决方案不保证线性时间，基于，在最坏的情况下可能需要 O(N*N)。

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

How to find the minimum possible cycle shift to take from s1 to s2?

python

string

algorithm

string-matching