学步园

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

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

 #include<string.h>  //C风格形式
 using namespace std;
 
 void 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)  
 //原型：extern char *strstr(char *haystack,char *needle);用法：#include<strng.h>
     {  cout<<"包含"<<endl;
        return ;
    }
   }
  // return false;
  cout<<"不包含"<<endl; 
 }

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

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

 #include<iostream>
 #include<string>
 
 using namespace std;
 
 bool rotstr(string src,string des)
 {
     string tmp = src;
     src=src+tmp;
     if(strstr(src.c_str(),des.c_str())==NULL)
     {
         return false;
     }
     return true;
 }
 
 int main()
 {
     string src="AABBCD";
     string des="DAAB";
     if(rotstr(src,des))
         cout<<"the string des is included in the rotated string of src "<<endl;
     else
         cout<<"the string des is not included in the rotated string of src "<<endl;
     return 0;
 }