C++程序检查是否可以通过旋转另一个字符串d个位置来获得字符串

在字符串处理中，经常会遇到两个字符串之间的判断问题。给定两个字符串s和t，我们想要检查t是否可以通过旋转s d个位置来获得。

例如，字符串s = “abcde”，t = “cdeab”，d = 2，则t可以通过旋转s 2个位置来获得。

解法一：暴力枚举

最简单的方法是将字符串t旋转d个位置，与字符串s进行比较，如果相等则说明t可以通过旋转s d个位置来获得。代码如下：

def is_rotated_string(s: str, t: str, d: int) -> bool:
    n = len(s)
    rotated_t = t[d:] + t[:d]
    return s == rotated_t

这段代码首先将字符串t进行旋转，然后再将s和旋转之后的字符串进行比较。

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

解法二：字符串拼接

我们可以发现，将字符串t旋转d个位置实际上相当于将t分为两个子串，并将这两个子串交换位置后再拼接在一起。例如，当d=2时，字符串t = “cdeab”可以被分为”cd”和”eab”两个子串，并将它们交换位置后拼接在一起得到”cdeab”。

所以，我们可以直接将t拼接在自己的尾部，然后取这个拼接后的字符串的第d个位置到第d+n个位置作为旋转之后的t。代码如下：

def is_rotated_string(s: str, t: str, d: int) -> bool:
    n = len(s)
    rotated_t = t + t
    return s == rotated_t[d:d+n]

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

解法三：KMP算法

KMP算法可以在O(n)时间内查找字符串中是否包含目标子串。我们可以将t旋转d个位置之后得到的字符串作为目标子串，将s作为原字符串进行匹配。如果s中存在一个子串与目标子串匹配，则说明t可以通过旋转s d个位置来获得。

代码如下：

from typing import List

def get_next(p: str) -> List[int]:
    n = len(p)
    next = [0] * n
    i, j = 1, 0
    while i < n:
        if p[i] == p[j]:
            i += 1
            j += 1
            next[i] = j
        elif j == 0:
            i += 1
        else:
            j = next[j]
    return next

def kmp(s: str, p: str) -> int:
    m, n = len(s), len(p)
    next = get_next(p)
    i, j = 0, 0
    while i < m and j < n:
        if s[i] == p[j] or j == 0:
            i += 1
            j += 1
        else:
            j = next[j]
    if j == n:
        return i - n
    else:
        return -1

def is_rotated_string(s: str, t: str, d: int) -> bool:
    n = len(s)
    rotated_t = t[d:] + t[:d]
    return kmp(s, rotated_t) != -1

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