首页 > 代码库 > 循环移动字符串

循环移动字符串

  这个问题的意思就是给定两个字符串s1和s2,判断s2是否包含在s1循环移位得到的字符串中。

  这个题的最简单的一种思路就是对s1进行循环穷举,对于得到的每种情况,都进行判断s2是否包含在其中。

  不过如果s1的字符串很长,那么穷举的时间复杂度是相当高的。因此可以换一种思路。

  新的解决办法相当的巧妙,假设我们在s1字符串前面再加入一个跟s1登场的空间,每当s1循环移动之后,就把移到末尾的字符在前面空间中加一个,那么情况如下所示:

  ABCD----ABCDA----ABCDAB----ABCDABC----ABCDABCD

  如果s2在s1的循环移位中,那么一定就在s1s1中。显然我们只需要多一个n的空间,即可将时间复杂度降到很低。