字符串移位包含的问题 2012-05-17 15:08:07

分类： C/C++

题目：给定两个字符串S1和S2，要求判断S2能否被S1做循环移位得到的字符串包含。

例如：s1=AABCD和S2=CDAA，返回true，s1=ABCD和s2=ACBD，返回false。

 

对于这个题目我给出了三种答案，

第一种：

通过创建一个和s2字符串大小一样的堆空间，然后将s1移位以后的字符串拷贝进去，然后再判断是否和s2相等，具体代码如下：

点击(此处)折叠或打开

1. /**
   
2. **    1表示包含, 0表示不包含
   
3. ** 我给的答案，出现很多次的字符串拷贝,已经额外的字符串分配空间
   
4. **/
   
5. int strcontain(const char* const str1, const char * const str2){
   
6.     if(NULL == str1 || NULL == str2)
   
7.         return 0;
   
8.         
   
9.     int len1, len2, i;
   
10.     char* tmp = NULL;
    
11.     len1 = strlen(str1);
    
12.     len2 = strlen(str2);
    
13.     
    
14.     if(len2 > len1)
    
15.         return 0;
    
16.     
    
17.     tmp = (char*)malloc(len2 + 1);
    
18.     memset(tmp, 0, len2 + 1);
    
19.     
    
20.     for(i = 0; i < len1; i++){
    
21.         if(len1 >= len2 + i)
    
22.             strncpy(tmp, str1 + i, len2);
    
23.         else{
    
24.             strncpy(tmp, str1 + i, len1 - i);
    
25.             strncpy(tmp + len1 - i, str1, len2 - len1 + i);
    
26.         }
    
27.         if(strcmp(tmp, str2) == 0){
    
28.             free(tmp);
    
29.             tmp = NULL;
    
30.             return 1;
    
31.         }
    
32.     }
    
33.     free(tmp);
    
34.     return 0;
    
35. }

第二种方法是编程之美上给出来的，代码如下：

点击(此处)折叠或打开

1. /**
   
2. **    code 2 提供的答案
   
3. **    额外的分配空间
   
4. **/
   
5. int code2(const char* const str1, const char* const str2){
   
6.     if(NULL == str1 || NULL == str2)
   
7.         return 0;
   
8.         
   
9.     int len1, len2, i;
   
10.     char* tmp = NULL;
    
11.     len1 = strlen(str1);
    
12.     len2 = strlen(str2);
    
13.     
    
14.     if(len2 > len1)
    
15.         return 0;
    
16.         
    
17.     tmp = (char*)malloc(len1 * 2);
    
18.     memset(tmp, 0, len1*2);
    
19.     strcpy(tmp, str1);
    
20.     
    
21.     for(i = 0; i < len1; i++){
    
22.         if(strncmp(tmp + i, str2, len2) == 0){
    
23.             free(tmp);
    
24.             tmp = NULL;
    
25.             return 1;
    
26.         }
    
27.         tmp[len1 + i] = str1[i];
    
28.     }
    
29.     
    
30.     free(tmp);
    
31.     tmp = NULL;
    
32.     return 0;
    
33. }

第三种方法和第一种其实非常相似，只是没有在额外的分配堆空间：

点击(此处)折叠或打开

1. /**
   
2. **    code3
   
3. **    不分配额外空间
   
4. **/
   
5. int code3(const char* const str1, const char* const str2){
   
6.     if(NULL == str1 || NULL == str2)
   
7.         return 0;
   
8.         
   
9.     int len1, len2, i;
   
10.     len1 = strlen(str1);
    
11.     len2 = strlen(str2);
    
12.     int comparelen = 0;
    
13.     
    
14.     if(len2 > len1)
    
15.         return 0;
    
16.     
    
17.     for(i = 0; i < len1; i++){
    
18.         if(len1 >= i + len2){
    
19.             if(strncmp(str1 + i, str2, len2) == 0)
    
20.                 return 1;
    
21.         }else{
    
22.             if((strncmp(str1 + i, str2, len1 - i) == 0)
    
23.             && strncmp(str1, str2 + len1 -i, len2 + i -len1) == 0)
    
24.                 return 1;
    
25.         }
    
26.     }
    
27.     
    
28.     return 0;
    
29. }