C语言实现字符串不重复相似字符计数的代码问题排查

问题描述 #

正在编写C语言程序，统计两个长度固定为4的字符串的相似字符数量，规则如下：

• 同一字母在两个串中重复出现不重复计数
• 两个字符串完全相同时直接返回4
• 预期计算逻辑示例：
  • 输入"week"和"weak"返回3，两词共有不重复字符为'w'、'e'、'k'
  • 输入"test"和"tast"返回2，两词共有不重复字符为't'、's'
    代码中实现了contains函数用于检查字符是否已经被统计，避免重复计数，但实际运行结果不符合预期，无法定位问题。
    原问题代码如下：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define STRLEN 4

bool contains(char tab[], char c){
    for(int i=0; i<STRLEN; i++){
        if(tab[i] == c){
            return 1;
        }
    }
    return 0;
}

int likeness(char* password, char* wordchosen) {

    if(strlen(password)!=STRLEN && strlen(wordchosen)!=STRLEN) {
        return -1;
    }

    if(!strcmp(password, wordchosen)) {
        return 4;
    }

    int like = 0;
    char found[STRLEN];

    for(int i=0; i<STRLEN; i++) {
        for(int j=0; j<STRLEN; j++) {
            /*printf("%c : %c\n", password[i], wordchosen[j]);
            printf("\n");*/
            if(password[i] == wordchosen[j] && !(contains(found, wordchosen[j]))) {
                like++;
            }
        }
        found[i] = password[i];
    }

    return like;
}

int main() {
    printf("week and week = %d\n", likeness("week", "week")); // should be 4 (same word even if only 3 (w, e, k))
    printf("test and tast = %d\n", likeness("test", "tast")); // should be 2 (t, s)
    printf("week and weak = %d\n", likeness("week", "weak")); // should be 3 (w, e, k)
    printf("snet and sent = %d\n", likeness("snet", "sent")); // should be 4 (s, n, e, t)
    printf("gree and green = %d\n", likeness("gree", "gren")); // should be 3 (g, r, e)
    printf("mail and main = %d\n", likeness("mail", "main")); // should be 3 (m, a, i)
    printf("same = %d\n", likeness("same", "same")); // should be 4
    // opposite side in the likeness func. return different result...
    return 0;
}

问题根因 #

代码共有4处逻辑错误：

1. 输入长度校验逻辑错误：原判断使用&&运算符，仅当两个字符串长度都不等于4时才返回错误，正确逻辑应为任意一个字符串长度不符合要求就返回-1，需要使用||运算符
2. found数组未初始化：栈上分配的局部数组默认存储随机垃圾值，直接传入contains做匹配判断会出现误判
3. 已统计字符的存入逻辑错误：原逻辑无论当前字符是否为两个串共有，都会在外层循环末尾将password[i]存入found，会把非共有字符错误标记为已统计
4. 计数逻辑漏洞：匹配到符合条件的共有字符时，仅做计数累加，没有将该字符存入found数组标记为已统计，后续重复匹配到同一字符时会重复计数

修复后代码 #

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define STRLEN 4

bool contains(char tab[], char c){
    for(int i=0; i<STRLEN; i++){
        if(tab[i] == c){
            return true;
        }
    }
    return false;
}

int likeness(char* password, char* wordchosen) {
    // 修复长度校验逻辑，任意一个串长度不对就返回错误
    if(strlen(password)!=STRLEN || strlen(wordchosen)!=STRLEN) {
        return -1;
    }

    if(!strcmp(password, wordchosen)) {
        return 4;
    }

    int like = 0;
    char found[STRLEN] = {0}; // 初始化数组全为'\0'，避免垃圾值干扰
    int found_pos = 0;

    for(int i=0; i<STRLEN; i++) {
        char cur = password[i];
        // 当前字符已经统计过直接跳过
        if(contains(found, cur)) {
            continue;
        }
        // 遍历第二个串查找当前字符是否存在
        for(int j=0; j<STRLEN; j++) {
            if(wordchosen[j] == cur) {
                like++;
                found[found_pos++] = cur; // 匹配到就标记为已统计
                break;
            }
        }
    }

    return like;
}

int main() {
    printf("week and week = %d\n", likeness("week", "week"));
    printf("test and tast = %d\n", likeness("test", "tast"));
    printf("week and weak = %d\n", likeness("week", "weak"));
    printf("snet and sent = %d\n", likeness("snet", "sent"));
    printf("gree and gren = %d\n", likeness("gree", "gren"));
    printf("mail and main = %d\n", likeness("mail", "main"));
    printf("same = %d\n", likeness("same", "same"));
    return 0;
}

修复后所有测试用例运行结果均符合预期。

内容的提问来源于stack exchange，提问作者Hangel