|
问题：给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。例如，S1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD，返回false。 解法一：从题目中可以看出，我们可以使用最直接的方法对S1进行循环移动，再进行字符串包含的判断，从而遍历其所有的可能性。字符串循环移动，时间复杂度为O（n），字符串包含判断，采用普通的方法，时间复杂度为O（n*m），总体复杂度为O（n*n*m）。字符串包含判断，若采用KMP算法，时间复杂度为O（n），这样总体的复杂度为O（n*n）。若字符串的长度n较大，显然效率比较低。其中n为S1的长度，m为S2的长度。  #include<iostream> using namespace std; /* strstr函数说明 包含文件：string.h 函数名: strstr 函数原型：extern char *strstr(char *str1, char *str2); 功能：从字符串str1中查找是否有字符串str2，如果有，从str1中的str2位置起，返回str1中str2起始位置的指针，如果没有，返回null。 返回值：返回该位置的指针，如找不到，返回空指针。 */ int rotate_conbine(char *src,char *dec) { int len=strlen(src); for(int i=0;i<len;i++) { char tmp=src[0]; for(int j=0;j<len-1;j++) { src[j]=src[j+1]; } src[len-1]=tmp; if(strstr(src,dec)!=NULL) return 1; } return 0; } int main() { char src[]="AABCD"; char dec[]="CDAA"; if(rotate_conbine(src,dec)) printf("ok\n"); else printf("no\n"); system("pause"); } strstr函数的内部代码是这样的： char *strstr( const char *s1, const char *s2 ) { if ( !(len2 = strlen(s2)) ) return (char *)s1; for(;*s1;++s1) { if ( *s1 == *s2 && strncmp(s1,s2,len2)==0 ) return (char *)s1; } return NULL; } 解法二：我们也可以对循环移位之后的结果进行分析。 #include<iostream> using namespace std; int rotate_conbine(string src,string des) { string tmp = src; src=src+tmp; if(strstr(src.c_str(),des.c_str())==NULL) { return 0; } return 1; } /* int doubel_src_conbine(char *src, char *des){ int len = strlen(src); char *temp = (char *)malloc((2*len+1)*sizeof(char)); char *p = temp; char *s = src; while(*s != '\0'){ *p = *s; p++; s++; } s = src; while(*s != '\0'){ *p = *s; p++; s++; } p++; *p = '\0'; if(strstr(temp, des) != NULL) return 1; else return 0; } */ int main() { char src[]="AABCD"; char dec[]="CDAA"; if(rotate_conbine(src,dec)) printf("ok\n"); else printf("no\n"); system("pause"); } 解法三：我们的想法是，在s1后面"虚拟"地接上一个s1，这个"虚拟的s1"并不占空间，但是仍然按照解法2的思路进行。那么，如何实现这个"虚拟的s1"呢？其实只要把s1的最后一个元素，再指回s1的第一个元素即可。这可以用取模运算实现。比如，元素s1[(d1+i) mod d1]其实就是那个“虚拟的s1”的第i个元素，这里 0<=i<=d1-1, d1是字符串s1的长度。 同理，指针也可以实现类似功能： #include<iostream> using namespace std; int ptr_contain(char *src, char *des){ char *p = NULL; char *q = NULL; char *r = NULL; p = q = src; r = des; char *tmp = NULL; while(*p != '\0' ) { while (*p != *r) p++; tmp = p; tmp++; while(*(++r) != '\0') { if(*(++p) == '\0') p = q; if(*r != *p) { r = des; p = tmp; break; } } if(*r == '\0') return 1; } return 0; } int main() { char src[]="AABCBCD"; char dec[]="CDAA"; if(ptr_contain(src,dec)) printf("ok\n"); else printf("no\n"); system("pause"); } 解法三的优点： |
|
|
