string - 检查一个字符串是否是另一个字符串的旋转而不连接

Question

有 2 个字符串，我们如何检查一个是否是另一个的旋转版本？

例如:你好--- lohel

一个简单的解决方案是通过连接第一个字符串与自身并检查另一个字符串是否是连接版本的子字符串。

还有其他解决办法吗？

我想知道我们是否可以使用循环链表？但我无法得出解决方案。

Answer 1

One simple solution is by concatenating them and checking if the other one is a substring of the concatenated version.

我假设你的意思是将第一个字符串与其自身连接起来，然后检查另一个字符串是否是该连接的子字符串。

那是行得通的，事实上根本不需要任何串联就可以完成。只需使用任何 string searching algorithm在第一个字符串中搜索第二个字符串，当你到达结尾时，循环回到开头。

例如，使用 Boyer-Moore整个算法将是 O(n)。