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

题目描述：

给定两个字符串s1和s2,要求判定s2是否能够被s1做循环移位得到的字符串包含。

解法一

穷举法：直接对s1进行循环移位，再进行字符串包含判断。
代码如下：

<span style="font-size:18px;">#include<iostream> 
#include<string.h>  
using namespace std;
 
int main()
{ 
	char src[] ="AABBCD";
	char des[] ="CDAA";
	 
	int len=strlen(src);
	for(int i=0;i<len;i++)
	{  
		char tempchar=src[0];
		for(int j=0;j<len-1;j++)
			src[j]=src[j+1];
		src[len-1]=tempchar;
		
		if(strstr(src,des)==0)  
		{  
			cout<<"包含"<<endl;
			return 0;
		}
	}
	cout<<"不包含"<<endl; 
	return 0;
}</span>

解法二：

分解s1的循环移位得到：
AABCD,ABCDA,BCDAA,CDAAB,.....
如果我们将前面移走的字符串保留下来，则有：
AABCD,AABCDA,AABCDAA,AABCDAAB,AABCDAABC,AABCDAABCD

实际对s1的循环移位得到的字符串实际为s1s1。
那么我们判断s2是否可以通过s1循环移位得到包含，
则只需要判断s1s1中是否含有s2即可以。
用提高空间复杂度来换取时间复杂度的减低的目的。
代码如下：

#include<iostream>
#include<string.h>
using namespace std;
 
bool isCon(char *s1, char *s2)
{
    char *temp=new char[strlen(s1)*2+1];
    strcpy(temp,s1);
    strcat(temp,s1);
    if(strstr(temp, s2)!=NULL)
        return true;
    else
        return false;
    delete[] temp;
}
 
int main()
{
     char *src="AABBCD";
     char *des="DAAB";
     if(isCon(src,des))
         cout<<"is included  "<<endl;
     else
         cout<<"is not included "<<endl;
     return 0;
}