字符串移位包含问题（来自openjudge的noi）

chenlifeng

描述
对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串s1和s2，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。例如CDAA是由AABCD两次移位后产生的新串BCDAA的子串，而ABCD与ACBD则不能通过多次移位来得到其中一个字符串是新串的子串。

输入
一行，包含两个字符串，中间由单个空格隔开。字符串只包含字母和数字，长度不超过30。
输出
如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串，则输出true，否则输出false。
样例输入
AABCD CDAA
样例输出
true



不知道为什么我一直过不了它的测试集，救救孩子。。
我的代码：

1. // noi 1.7 19 字符串移位包含问题
   
2. #include<stdio.h>
   
3. #include<stdlib.h>
   
4. #include<string.h>
   
5. 
   
6. int main(void) {
   
7.         char s1[35] = {}, s2[35] = {};
   
8.         int i = 0, j = 0, found = 0, len1 = 0, len2 = 0;
   
9.         scanf("%s", s1);                               
   
10.         scanf("%s", s2);
    
11.         len1 = strlen(s1);
    
12.         len2 = strlen(s2);
    
13.        
    
14.         // part_1 : s2 是否为 s1 的子串
    
15.         for(i = 0 ; s1[i] != '\0' ; ++i) {
    
16.                 found = 0;
    
17.                 for(j = 0 ; s2[j] != '\0' ; ++j) {
    
18.                         if(s1[(i + j) < len1 ? (i + j) : (i + j - len1 )] != s2[j]) {
    
19.                                 found = 1;
    
20.                                 break;
    
21.                         }
    
22.                 }
    
23.                 if( ! found ) {
    
24.                         printf("true");
    
25.                         return 0;
    
26.                 }
    
27.         }
    
28.        
    
29.         // part_2 : s1 是否为 s2 的子串
    
30.         for(i = 0 ; s2[i] != '\0' ; ++i) {
    
31.                 found = 0;
    
32.                 for(j = 0; s1[j] != '\0' ; ++j) {
    
33.                         if(s2[(i + j) < len2 ? (i + j) : ( i + j - len2 )] != s1[j]) {
    
34.                                 found = 1;
    
35.                                 break;
    
36.                         }
    
37.                 }
    
38.                 if( ! found ) {
    
39.                         printf("true");
    
40.                         return 0;
    
41.                 }
    
42.         }
    
43.        
    
44.         printf("false");
    
45.         return 0;
    
46. }

复制代码

jhq999

刚开始没看出毛病，除了习惯不一样
//****应该是缺这个条件语句&&len1>=len2，会出现str1="ABBCA",str2="ABBCAABBCAABBCA"的情况,if(s1[(i + j) < len1 ? (i + j) : (i + j - len1 )] != s2[j]) 越界****

1. for(i = 0 ; s1[i] != '\0'&&len1>=len2 ; i++) {//比如这个i++和++i的效果一样，因为只是自增运算，不涉及其他运算。所以先加后加没有影响。
   
2. //****应该是缺这个条件语句&&len1>=len2，会出现str1="ABBCA",str2="ABBCAA"的情况****
   
3.                 found = 0;
   
4.                 for(j = 0 ; s2[j] != '\0' ; ++j) {
   
5.                         if(s1[(i + j) %len1] != s2[j]) {//比如这个，效果也一样，当然len2>=2*len1楼主那个就越界了
   
6.                                 found = 1;
   
7.                                 break;
   
8.                         }
   
9.                 }
   
10.                 if( ! found ) {
    
11.                         printf("str2 是 str1的子串");//这里没有明确到底谁是谁的子串，但是样例也没表示错误
    
12.                         return 0;
    
13.                 }
    
14.         }

复制代码

傻眼貓咪

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. int isSubString(char str1[], char str2[], int a, int b){
   
5.         int flag;
   
6.         if(b > a) return 0;
   
7.         else{
   
8.                 for(int i = 0; i < a; i++){
   
9.                         flag = 1;
   
10.                         for(int j = i, k = 0; j < i+b; j++, k++){ // 切片，长度一致
    
11.                                 if(str1[j%a] != str2[k]){ // 判断两个字符串是否一样
    
12.                                         flag = 0;
    
13.                                         break;
    
14.                                 }
    
15.                         }
    
16.                         if(flag) return 1;
    
17.                 }
    
18.         }
    
19.         return 0;
    
20. }
    
21. 
    
22. int main(){
    
23.         char str1[30], str2[30];
    
24.         int a, b, x, y;
    
25.         scanf("%s%s", str1, str2);
    
26.         a = strlen(str1);
    
27.         b = strlen(str2);
    
28.         x = isSubString(str1, str2, a, b);
    
29.         y = isSubString(str2, str1, b, a);
    
30.         printf(x || y ? "true" : "false");
    
31.         return 0;
    
32. }

复制代码

chenlifeng

jhq999 发表于 2021-12-20 06:45
刚开始没看出毛病，除了习惯不一样
//****应该是缺这个条件语句&&len1>=len2，会出现str1="ABBCA",str2="A ...

输入的字符串长度最大为30，我定义的长度为35，应该不会出现越界啊，字符数组的后面是接了终止符'\0'的，上面举的例子第三轮比较的开始就会是str1的’\0' 和 str2的 'A' 进行比较，比较到这里两个字符就应该会不相等跳出当前循环啊

jhq999

chenlifeng 发表于 2021-12-20 16:15
输入的字符串长度最大为30，我定义的长度为35，应该不会出现越界啊，字符数组的后面是接了终止符'\0'的， ...

在第二层循环越界，第二层循环没有

1. s1[i]!='\0'

复制代码

的条件

chenlifeng

jhq999 发表于 2021-12-20 17:15
在第二层循环越界，第二层循环没有的条件

                 for(j = 0 ; s2[j] != '\0' ; ++j) {
                        if(s1[(i + j) < len1 ? (i + j) : (i + j - len1 )] != s2[j]) {
                                found = 1;
                                break;
                        }
                }
但是在第二层循环中当读到了s1 [ i ] = ‘\0‘的时候，因为已经控制了s2 [ j ] ！=’\0', 则会有s1 [ i ] != s2 [ j ], 于是执行if语句块中的break, 不就不会继续第二层循环造成数组的越界了吗？

jhq999

chenlifeng 发表于 2021-12-20 18:36
for(j = 0 ; s2[j] != '\0' ; ++j) {
                        if(s1[(i + j) < len ...

的确