A method isSubstring which checks if one word is a substring of another, use this method to check if two strings are rotated.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

/****************************************************************************************** ******************************************************************************************* Chapter 1 Arrays and Strings * 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") By: Hamed Kiani (July 20, 2015) ****************************************************************************************** ******************************************************************************************/ #include<iostream> #include<cstring> using namespace std; bool is_sub_string(const char* s1, const char* s2) { // check if two strings are not null if (!s1 || !s2) return false; // find the first char of s2, s2[0] in the s1, if found then check the rest of s2 over s1 int i,j ; j = 0; for (i = 0; s1[i] != '\0'; i++) { if (s1[i] == s2[0]) { for(j = 1; s2[j] != '\0'; j++) // we are already sure that s1[i] == s2[0] if (s2[j] != s1[i+j]) break; } // if (s2[j] == '\0') means that we have similar chars till the end of s2 if (s2[j] == '\0') return true; } // is not s sub string return false; } // O(n) time, O(1) additional space. bool is_rotation_fun1(const char* s1, const char* s2) { if (!s1 || !s2) return false; if (strlen(s1) != strlen(s2)) return false; while(*s2 != '\0') s2++; s2--; while(*s1 != '\0') { if (*s1 != *s2) return false; s1++; s2--; } return true; } // O(n) time, O(n) additional space. // using is_rotation function // the trick is that we append the inverse of s1 to s1 and then check: // if is_sub_string(s1+inv(s1[1:length(s1)-1]), s2). // name + man = nameman // is is_sub_string(nameman, eman) bool is_rotation_fun2( char* s1, char* s2) { int l1; l1 = strlen(s1); char* temp = (char *) malloc( sizeof(char) * l1 * 2); char *t1 = s1; int i = 0; while(*t1 != '\0') { temp[i] = *t1; t1++; i++; } // move t1 pointin to end of s1 to next to last char. // accordingly, we change l1 = l1 -2, since we ignore the last char of s1 //and consider length counter as [0...strlen(s1)-1] t1 -= 2; l1 -= 2; while(l1>=0) { temp[i] = s1[l1]; l1--; i++; } bool check = is_sub_string(temp, s2); free(temp); return check; } void main() { char str1[] = "check this string"; char str2[] = "this"; bool check ; check = is_sub_string(str1,str2); cout << check << endl; char str3[] = "siht"; check = is_rotation_fun1(str3, str2); cout << check << endl; check = is_rotation_fun2(str3, str2); cout << check << endl; }