3.1　字符串移位包含的问题

给定两个字符串s₁和s₂，要求判定s₂是否能够被通过s₁作循环移位（rotate）得到的字符串包含。例如，给定s₁＝AABCD和s₂＝CDAA，返回true；给定s₁＝ABCD和s₂＝ACBD，返回false。

分析与解法

【解法一】

从题目中可以看出，我们可以使用最直接的方法对s₁进行循环移位，再进行字符串包含的判断，从而遍历其所有的可能性。

因此，可以用如下的代码实现：

代码清单3-1

如上，穷举s₁（如ABCD）做循环移位（rotate）所能得到的所有字符串，看其结果是否与s₂相等。若字符串的长度N较大，显然效率很低。

【解法二】

我们也可以对循环移位之后的结果进行分析。

以s₁＝ABCD为例，先分析对s₁进行循环移位之后的结果，如下所示：

ABCD→BCDA→CDAB→DABC→ABCD…

假设我们把前面移走的数据进行保留，会发现有如下的规律：

ABCD→ABCDA→ABCDAB→ABCDABC→ABCDABCD

因此，可以看出对s₁做循环移位（rotate）所得到的字符串都将是字符串s₁s₁的子字符串。如果s₂可以由s₁循环移位（rotate）得到，那么s₂一定在s₁s₁上。至此我们将问题转换成考察s₂是否在s₁s₁上，可通过调用一次strstr^①函数得到结果。

例如若CDAB在ABCDABCD上可以找到，那么CDAB也可通过ABCD做循环移位得到（ABCD循环左移或循环右移两位）。

总结

第二种方法利用了“提高空间复杂度来换取时间复杂度的降低”的思路，适用于对时间复杂度要求高的场合。