编程之美3.1 字符串移位包含的问题

做完LeetCode 189. Rotate Array之后 想起了编程之美上也有一个类似的题目，拿过来一块重温总结一下。
题目描述：
给定两个字符串s1和s2，要求判定s2是否能够被s1做循环移位得到的字符串包含。例如给定s1=AABCD和s2=CDAA，返回true;给定s1=ABCD和s2=ACBD，返回false。
解法1:
对s1做循环移位，没移动一次就判断是否包含s2，具体代码如下：
[cc lang=”C++”]
#include
#include
#include
#include
using namespace std;

//编程之美3.1判断s1移位后形成的字符串是否包括字符串s2

bool is_contained(string str1, string str2)
{
int len = str1.size();
bool flag = false;
for(int i=0; i < len; i++) { char temp = str1[len-1]; for(int index = len-1; index >0; index –)
{
str1[index] = str1[index-1];
}
str1[0] = temp;
cout << "循环移位后得到的字符串： " << str1 << endl; if(str1.find(str2) != string::npos) { flag = true; break; } } return flag; } int main() { string str1 = "AABCD"; string str2 = "CDAA"; bool flag = is_contained(str1, str2); cout << "flag:" << flag << endl; return 0; } [/cc] 解法2: 另外可以对移位后的结果进行分析。以s1=ABCD为例 ABCD->DABC->CDAB->BCDA->ABCD
假设我们把前面移走的元素保留，会发现有如下规律：
ABCD->DABCD->CDABCD->BCDABCD->ABCDABCD
由此可以看出，对s1做循环移位所得到的字符串都将是字符串s1s1的子字符串。如果s2可以由s1循环移位得到，那s2一定在s1s1上，只需要一次字符串的查找操作即可。