确定字符串是否是另一个的旋转

假设我们有两个字符串s1和s2，我们需要确定s2是否是通过将s1旋转而得到的。我们可以将s1复制一遍并连接在一起，得到s1s1。如果s2是s1的旋转，则s2必定是s1s1的子字符串。

以下是Python实现：

def is_rotation(s1, s2):
    if len(s1) != len(s2):
        return False
    s1s1 = s1 + s1
    return s2 in s1s1

时间复杂度为O(n)，其中n为字符串的长度。

相关问题

请设计一个线性时间的算法，判断字符串 S 是否是另一个字符串 S’ 的循环旋 转。例如， arc 和 car 是彼此的循环旋转。

可以使用滑动窗口法（Sliding Window）来设计一个线性时间复杂度的算法来判断字符串 `S` 是否是字符串 `S'` 的循环旋转。以下是步骤：

1. **初始化**：
- 定义两个指针，`i` 和 `j`，都初始化为0。
- 创建两个临时变量 `length1` 和 `length2`，分别存储 `S` 和 `S'` 的长度。

2. **比较字符**：
- 当 `i < length1` 且 `j < length2` 时，不断移动指针：
- 如果 `S[i]` 等于 `S'[j]`，则将 `i` 和 `j` 都加一。
- 否则，检查下一个字符：如果 `S[i] == S'[j+length2-length1]`，说明 `S` 可能是 `S'` 的循环旋转，因为当前子串 `[S[i], ..., S[length1-1]]` 之后可能是 `[S'[length2-length1], ..., S'[length2-1], S'[0], ..., S'[j-1]]` 这样形成了循环。
- 更新 `j = j + length2-length1`。
- 如果不是循环旋转，则只移动 `i` 指针。

3. **结束条件**：
- 当指针相遇（`i == j`），表示找到了一个可能的循环旋转部分；或者当遍历完 `S` 但没有找到匹配，即 `i >= length1` 而 `j < length2`，表明 `S` 不是 `S'` 的循环旋转。

4. **优化判断**：
- 如果找到匹配，为了确认是否是循环旋转，只需再比较一次 `S` 的剩余部分与 `S'` 的前一部分，看它们是否完全相等。

以下是伪代码形式：

function isCycleRotation(S, S'):
    length1 = len(S)
    length2 = len(S')
    
    i = j = 0
    while i < length1 and j < length2:
        if S[i] == S'[j]:
            i += 1
            j += 1
        else:
            if i < length1 and S[i] == S'[j + (length2 - length1)]:
                j = j + length2 - length1
            else:
                return False
    
    # Check for complete cycle if i equals length1
    if i == length1:
        return S[i:] == S'[:length2]
    
    return False