这个问题的意思就是给定两个字符串s1和s2,判断s2是否包含在s1循环移位得到的字符串中。
这个题的最简单的一种思路就是对s1进行循环穷举,对于得到的每种情况,都进行判断s2是否包含在其中。
不过如果s1的字符串很长,那么穷举的时间复杂度是相当高的。因此可以换一种思路。
新的解决办法相当的巧妙,假设我们在s1字符串前面再加入一个跟s1登场的空间,每当s1循环移动之后,就把移到末尾的字符在前面空间中加一个,那么情况如下所示:
ABCD----ABCDA----ABCDAB----ABCDABC----ABCDABCD
如果s2在s1的循环移位中,那么一定就在s1s1中。显然我们只需要多一个n的空间,即可将时间复杂度降到很低。