我正在尝试写一个更简单的版本的Boyer摩尔算法，没有前缀函数。它必须打印所有与模式比较的符号的位置。并且在本地它通过了测试，但是当我提交到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 ..型
3条答案
按热度按时间7rfyedvj1#
差异（输出末尾多了一个数字28）可能是由于输入的最后一行末尾缺少一个换行符（
\n）造成的。我能够在本地复制你的两个输出（有28和没有28）。字符串
TL;DR通过将
(ch = getchar()) == '\n'更改为(ch = getchar()) == EOF || ch == '\n'，并将#define ALPH_SIZE 128更改为#define ALPH_SIZE 256来修复代码中的错误。可能还有其他bug，我还没有检查。如果你遇到其他bug，请在StackOverflow上单独提问。
这个答案的其余部分解释了我是如何诊断这个bug的。
AddressSanitizer
gcc -fsanitize=address）在缺少换行符时显示内存访问问题：型
请注意，我不得不重复多次以触发AddressSanitizer错误消息。
大多数情况下，这是由程序中的错误引起的，通常是未定义的行为。AddressSanitizer输出中的
in search /tmp/t.c:33子句指示错误读取发生在源代码中的何处（即第33行，函数search）。我在你的代码中添加了一些额外的
printfs，看看第33行发生了什么。输出是：型
罪魁祸首是最后一次读访问：
str[-369011759] == ??，这表明shift + j变成了-369011759，这显然是不正确的，因为正确的值是小的非负整数。请注意，我不得不重复多次以触发Address Sanitizer错误消息，并且每次的数字-369011759都不同。
看起来
j有一个正常的值6。要找出实际的bug，下一步是检查shift在哪里得到它的大负值。在这一点上，输出行
str[27] == 255对我来说是可疑的。我检查了您的代码是否正确处理了str中的如此大的值，然后我发现了一个bug。修复这个新发现的bug的一种方法是将
ALPH_SIZE从128更改为256。（我已经验证了它会使地址消毒器错误消失。）原因如下。第39行包含badchar[str[shift + j]]的读取。要使其有效，我们需要0 <= str[shift + j] && str[shift + j] < ALPH_SIZE，因为ALPH_SIZE是badchar数组的大小。然而，str[...]是255（因为它是无符号字符），因此我们需要ALPH_SIZE >= 256。实际上，越界数组访问（读或写）在C中是未定义的行为。
型
，我还将第28行改为使用malloc：
型
，之后我还添加了
free(badchar)。型
实际上，AddressSanitizer的输出指出了第39行中的bug，而额外的
fprintf调用的输出确认这是一个越界的数组访问：阅读数组badchar的元素255，该数组只有128个元素。我们是怎么得到
str[27] == 255的（因此阅读badchar[255]）？这很简单：如果在阅读str时，在文件的末尾没有终止\n，则getchar()返回“0”，当分配给unsigned char时，“0”变为255。（如上所述，明显的修复方法是在x1处停止，并将ALPH_SIZE更改为256。为什么AddressSanitizer没有报告读取越界数组索引问题（作为stack-buffer-overflow）在
badchar之前的第39行被更改为使用malloc（报告为堆缓冲区溢出）？我还不太明白这一点。AddressSanitizer应该能够可靠地报告堆栈缓冲区溢出。可能这取决于GCC和Clang版本，因为将命令gcc更改为clang使堆栈缓冲区溢出错误可靠地出现。可能升级到最新的GCC和Clang会有所帮助。Valgrind在检测堆栈缓冲区溢出读取方面不如AddressSanitizer可靠。b5buobof2#
你的
read_str()函数在两个方面有缺陷：1.它不识别或处理标准输入的文件结尾。当程序的标准输入连接到终端时，通常不会遇到这种情况，但如果输入从常规文件或管道（例如）重定向，则完全可能出现这种情况。这可能会导致字符串结尾处出现不需要的额外字符。
1.它不会向最大长度输入添加字符串结束符。
而这些合并，因为如果
read_str()确实到达了文件结尾，那么它将始终表现得好像它收到了一个最大长度的输入，因此无法终止它。终止失败将导致程序在其他地方表现出未定义的行为，但问题的根源是
read_str()。我的第一个建议是完全转储read_str()，并使用标准fgets()：字符串
但是如果你坚持使用自己的
read_str()，并且参数具有代码所隐含的语义，那么你需要纠正上面描述的两个问题。例如：型
hsvhsicv3#
存在多种问题：
ALPH_SIZE被定义为128，它不是unsigned char类型的范围。您应该使用(UCHAR_MAX+1)，或256表示8位字节，以允许badchar数组处理字符串中超过127的字符，如UTF-8前导和连续字节或其他非ASCII内容。这是潜在的未定义行为。read_str作为参数max_len，如果你在到达max_len字符之前读取了一个换行符，那么你只会空终止这个数组。这是容易出错的：它可能不会在发布的代码中引起问题，但不推荐这样做，特别是当你显式地空终止较短的字符串时。read_str中的阅读循环不会在文件结束时停止，因为您只测试'\n'。如果输入的最后一行没有以换行符结束，则循环将继续尝试从stdin读取，从getchar()接收EOF并存储'\377'（即：0xff或255）到数组中，后来导致未定义的行为，因为数组badchar太短，无法处理这些字节值。