无前缀函数的简化Boyer-Moore算法存在未定义行为问题

我正在实现一个不含前缀函数的简化版Boyer-Moore算法，要求打印所有与模式串比对的字符位置。本地测试正常，但提交到GitLab后测试失败，输出末尾出现垃圾数据，无法定位未定义行为的原因。

代码实现 #

#include <stdio.h>

#define MAX_PATTERN_LEN 16
#define BUF_SIZE 69
#define ALPH_SIZE 128

int read_str(int max_len, unsigned char *str_place) {
    int count_read = 0;
    for (int i = 0, ch; i < max_len; i++) {
        if ((ch = getchar()) == '\n') {
            str_place[i] = '\0';
            break;
        }
        str_place[i] = (char)ch;
        count_read++;
    }
    return count_read;
}

void calculate_shifts(const unsigned char *str, int len_str, int *badchar) {
    for (int i = 0; i < ALPH_SIZE; i++)
        badchar[i] = len_str;
    for (int i = 0; i < len_str - 1; i++)
        badchar[str[i]] = len_str - 1 - i;
}

void search(const unsigned char *str, const unsigned char *patt, int len_patt, int len_str) {
    int badchar[ALPH_SIZE];
    calculate_shifts(patt, len_patt, badchar);
    int shift = 0;
    while (shift <= (len_str - len_patt)) {
        int j = len_patt - 1;
        for (; j >= 0 && patt[j] == str[shift + j]; j--)
            printf("%d ", shift + j + 1);
        if (j < 0) {
            shift += ((shift + len_patt) < len_str) ? badchar[patt[len_patt - 1]] : 1;
        } else {
            printf("%d ", shift + j + 1);
            int shift_addition = badchar[str[shift + j]];
            if ((shift_addition == len_patt) && (j < len_patt - 1) && (patt[len_patt - 1] == patt[0]))
                shift_addition--;
            shift += shift_addition;
        }
    }
}

int main(void) {
    unsigned char str[BUF_SIZE + 1];
    unsigned char patt[MAX_PATTERN_LEN + 1];
    int len_patt = read_str(MAX_PATTERN_LEN + 1, patt);
    int len_str = read_str(BUF_SIZE + 1, str);
    if (!len_patt || !len_str)
        return 0;
    search(str, patt, len_patt, len_str);
    return 0;
} 

测试用例 #

example
this is simple example

预期输出 #

7 14 13 12 11 10 20 22 21 20 19 18 17 16

实际输出 #

7 14 13 12 11 10 20 22 21 20 19 18 17 16 28 ..

问题分析与修复 #

核心问题：read_str函数未处理EOF及字符串终止符 #

1. 未处理EOF情况：当输入流到达EOF（而非换行符）时，getchar()返回EOF，原代码不会触发break，会将EOF转换为char（通常为0xff）存入数组，并且继续计数直到达到max_len，导致len_str被错误地计算为max_len，而非实际有效字符长度。
2. 未处理满长度输入的终止符：当输入字符数刚好达到max_len时，循环结束后未手动添加字符串终止符'\0'，虽然当前search函数依赖len_str访问，但可能导致后续未定义行为。

修复后的read_str函数 #

int read_str(int max_len, unsigned char *str_place) {
    int count_read = 0;
    for (int i = 0, ch; i < max_len; i++) {
        ch = getchar();
        // 同时处理换行符和EOF
        if (ch == '\n' || ch == EOF) {
            str_place[i] = '\0';
            break;
        }
        // 使用unsigned char存储，避免符号扩展问题
        str_place[i] = (unsigned char)ch;
        count_read++;
    }
    // 当输入填满整个缓冲区时，手动添加终止符
    if (count_read == max_len) {
        str_place[max_len] = '\0';
    }
    return count_read;
}

额外优化 #

• 将str_place[i] = (char)ch改为(unsigned char)ch，避免EOF转换为char时的符号扩展问题，符合unsigned char数组的定义。

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