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+str1

    if(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;

}