Careercup its 1.8 serial shift includes problems

Hello everyone , I meet you again , I'm the king of the whole stack , I've prepared for you today Idea Registration code .

【 The title of 】

original text ：

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”).

translation ：

If you have one isSubstring function , It can detect whether a string is a substring of another string . Give the string s1 and s2. Just use it once isSubstring Can infer s2 Whether it is s1 Rotation string for , Please write the code . Rotate string ：”waterbottle” yes ”erbottlewat” Rotation string for .

【 analysis 】

We can also analyze the results after cyclic shift . With S1 = ABCD For example , First analyze the right S1 The result of cyclic shift , As you can see below ： ABCD—>BCDA—->CDAB—->DABC—->ABCD…… If we keep the previously removed data . You will find, for example, the following rules ： ABCD—>ABCDA—->ABCDAB—->ABCDABC—->ABCDABCD…… therefore , Can see right S1 The string obtained by cyclic shift will be a string S1S1 Substring of .

hypothesis S2 Can be made by S1 Cyclic shift results in , that S2 It must be S1S1 On , In this way, the time complexity is reduced .

Same topic ： The beauty of programming string shifting includes problems

【 Code 1 】

/*********************************
*    date ：2014-5-15
*    author ：SJF0115
*    Question no :  String shifting includes problems 
*    source ：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;
}

Copy

【 Code 2 】

/*********************************
*    date ：2014-5-15
*    author ：SJF0115
*    Question no :  String shifting includes problems 
*    source ：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;
}

Copy

Copyright notice ： This article is an original blog article , Blog , Without consent , Shall not be reproduced .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117665.html Link to the original text ：https://javaforall.cn