If string str1 is a rotation of string str2, it must holds two conditions:
- The length of str1 equals to the length of str2;
- There is at least a set of two string A and B, such that str1=AB and str2=BA. We double str1, and get a new string as ABAB. If str2 is a rotation of str1, str2 must be a substring of this new string.
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 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-04-11 17:49 # Filename: 1.8.c # Description: check if a string is a rotation of another string =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <string.h> int isRotation(char *str1, char *str2){ // Input: two string as str1 and str2 // Output: -1 for error // 0 for they are not rotation to each other // 1 for they are rotation to each other // Function: check whether these two strings are // rotation to each other char *str_twice = NULL; int str1_len = 0, str2_len = 0; if(str1 == NULL || str2 == NULL){ return -1; } str1_len = strlen(str1); str2_len = strlen(str2); if(str1_len != str2_len){ // If they are rotation to each other, the length // of them must be the same. return 0; } // Allocate memory for two str1, and fill it with two str1 // such that, str_twice = str1 + str1 str_twice = (char *)malloc(str1_len*2+1); if(str_twice == NULL){ return -1; } strncpy(str_twice, str1, str1_len); strncpy(str_twice+str1_len, str1, str1_len); str_twice[str1_len*2] = ' '; // Try to find str2 in str_twice. // If successfully, they are rotation // Otherwise, they are not. if(strstr(str_twice,str2) == NULL){ free(str_twice); return 0; } else{ free(str_twice); return 1; } } int main(int argc, char *argv[]){ int ret = 0; if(argc != 3){ printf("Usage: %s string1 string2n",argv[0]); return -1; } ret = isRotation(argv[1],argv[2]); if( ret == 1 ){ printf("They are rotations to each other:n%sn%sn", argv[1], argv[2]); } else if( ret == 0){ printf("They are NOT rotations to each other:n%sn%sn", argv[1], argv[2]); } else{ printf("Erro in rotation checking:n%sn%sn", argv[1], argv[2]); } return 0; } |