UVA OJ 455提交获WA，求程序错误原因及修正方法

题目描述 #

若一个字符串可由长度为k的子串重复拼接一次或多次得到，则称该字符串的周期为k。例如，字符串“abcabcabcabc”的周期为3（由“abc”重复4次构成），同时也有周期6（“abcabc”重复2次）和12（自身重复1次）。编写程序读取字符串，确定其最小周期。
输入：第一行输入整数N表示测试用例数，随后空一行。每个测试用例为一个最多80个非空白字符的字符串，连续测试用例间空一行。
输出：每个测试用例输出最小周期整数，连续输出间空一行。
样例输入：

1
HoHoHo

样例输出：

2

我的问题 #

我已经测试了所有能想到的用例，程序返回结果都正确，但在线评测（OJ）还是判Wrong Answer（WA）。附上我的代码，我标记了一处可能错误的地方，请问问题出在哪里？

#include <stdio.h>
#include <string.h>
#define maxn 85
int check(char* s, int per){
    for(int i = 0; i < strlen(s) - per; i++){
        if(s[i + per] != s[i]) return 0;
    }
    return 1;
}
int main(){
    int T;
    scanf("%d", &T);
    char s[maxn];
    while(T--){
        scanf("%s", s);
        int len = strlen(s);
        bool OK = false;
        for(int i = 1; i <= len/2 && (len % i == 0); i++){//That's wrong.
            if(check(s, i)){
                printf("%d\n", i);
                OK = true;
                break;
            }
        }
        if(!OK) printf("%d\n", len);
        if(T) printf("\n");
    }
    return 0;
}

问题分析与修正 #

你标记的那一行确实是核心错误！我们来拆解问题：

1. 循环条件的逻辑错误 #

你把len % i == 0和i <= len/2用&&连接在for循环的条件里，这会导致只要某个i不满足len%i==0，整个循环就直接终止，而不是跳过当前i继续检查下一个可能的周期值。

举个例子：假设字符串长度是18，最小周期是6。当i=4时，18%4≠0，此时循环条件i<=9 && 18%4==0为false，循环直接退出，不会继续检查i=5、6这些后续值，最终程序会错误地输出18（字符串自身长度），而正确答案是6。

正确的做法是把len%i==0的判断移到循环体内部，循环条件只保留i <= len/2：

for(int i = 1; i <= len/2; i++){
    if(len % i == 0 && check(s, i)){
        printf("%d\n", i);
        OK = true;
        break;
    }
}

2. 其他潜在问题 #

• 缺少bool类型的头文件：C语言中bool类型定义在<stdbool.h>里，不包含这个头文件可能导致编译器处理异常，建议添加#include <stdbool.h>。
• check函数重复计算字符串长度：strlen(s)在循环中被多次调用，效率较低，建议提前把长度存到变量里：

  int check(char* s, int per){
      int len = strlen(s);
      for(int i = 0; i < len - per; i++){
          if(s[i + per] != s[i]) return 0;
      }
      return 1;
  }
  

• 输入空行处理：虽然scanf("%s")会自动跳过空白字符，但部分OJ的测试用例可能存在多空行的情况，用fgets配合空行过滤会更稳妥（可选优化）。

修正后的完整代码 #

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define maxn 85

int check(char* s, int per){
    int len = strlen(s);
    for(int i = 0; i < len - per; i++){
        if(s[i + per] != s[i]) return 0;
    }
    return 1;
}

int main(){
    int T;
    scanf("%d", &T);
    getchar(); // 吃掉输入T后的换行符
    char s[maxn];
    
    while(T--){
        // 读取字符串并过滤空行
        fgets(s, maxn, stdin);
        int len = strlen(s);
        if(s[len-1] == '\n'){
            s[len-1] = '\0';
            len--;
        }
        // 处理测试用例间的空行
        while(len == 0){
            fgets(s, maxn, stdin);
            len = strlen(s);
            if(s[len-1] == '\n'){
                s[len-1] = '\0';
                len--;
            }
        }
        
        bool OK = false;
        for(int i = 1; i <= len/2; i++){
            if(len % i == 0 && check(s, i)){
                printf("%d\n", i);
                OK = true;
                break;
            }
        }
        if(!OK) printf("%d\n", len);
        if(T) printf("\n");
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Leon.L