本文主要是介绍CareerCup之1.8 字符串移位包含问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目】
原文：
1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring ( i.e., “waterbottle” is a rotation of “erbottlewat”).
译文：
假设你有一个isSubstring函数，可以检测一个字符串是否是另一个字符串的子串。 给出字符串s1和s2，只使用一次isSubstring就能判断s2是否是s1的旋转字符串， 请写出代码。旋转字符串："waterbottle"是"erbottlewat"的旋转字符串。
【分析】
我们也可以对循环移位之后的结果进行分析。
以S1 = ABCD为例，先分析对S1进行循环移位之后的结果，如下所示：
ABCD--->BCDA---->CDAB---->DABC---->ABCD……
假设我们把前面的移走的数据进行保留，会发现有如下的规律：
ABCD--->ABCDA---->ABCDAB---->ABCDABC---->ABCDABCD……
因此，可以看出对S1做循环移位所得到的字符串都将是字符串S1S1的子字符串。如果S2可以由S1循环移位得到，那么S2一定在S1S1上，这样时间复杂度就降低了。
同样题目：编程之美之字符串移位包含问题
【代码一】
/*********************************
* 日期：2014-5-15
* 作者：SJF0115
* 题号: 字符串移位包含问题
* 来源：CareerCup
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;bool isSubstring(char* str1,char* str2){if(str1 == NULL || str2 == NULL){return false;}if(strstr(str1,str2) != 0){return true;}return false;
}bool IsRotate(char* str1,char* str2){int i,j;if(str1 == NULL || str2 == NULL){return false;}int len1 = strlen(str1);char* str3 = new char(len1*2+1);strcpy(str3,str1);strcat(str3,str1);//str3 = str1+str1if(isSubstring(str3,str2)){return true;}return false;
}int main(){char str1[6] = "AABCD";char str2[5] = "CDAA";bool result = IsRotate(str1,str2);cout<<result<<endl;return 0;
}
【代码二】
/*********************************
* 日期：2014-5-15
* 作者：SJF0115
* 题号: 字符串移位包含问题
* 来源：CareerCup
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;bool isSubstring(string str1,string str2){if(str1.find(str2) != string::npos) {return true;}return false;
}bool IsRotate(string str1,string str2){string str3 = str1+str1;if(isSubstring(str3,str2)){return true;}return false;
}int main(){string str1 = "apple";string str2 = "pleap";bool result = IsRotate(str1,str2);cout<<result<<endl;return 0;
}
这篇关于CareerCup之1.8 字符串移位包含问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
