我编写了这个小程序，以在较大的字符串中查找子字符串的所有出现，或者在草堆中查找针。当我在本地运行程序时，它似乎运行得很好。然而，当我把它提交给一个在线比赛进行评判时，它会给出一个SIGBART错误。我认为这是因为内存管理不善，所以我删除了free()函数调用，但随后我得到了一个超过时间限制的错误（但SIGBART错误消失了）。删除free()调用会减慢程序速度吗？我的程序有漏洞吗？
这是我所说的比赛：干草堆中的针
这是代码：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define RAW_INPUT_SIZE 10000
#define BOOL unsigned int
#define NO 0
#define YES 1
int main (int argc, char **argv)
{
int needleLength;
char *rawNeedle = (char *)malloc(RAW_INPUT_SIZE);
char *rawHaystack = (char *)malloc(RAW_INPUT_SIZE);
char *needle; // to be allocated later
char *haystack; // to be allocated later, but not deallocated
while (scanf("%in%sn%s", &needleLength, rawNeedle, rawHaystack) != EOF)
{
needle = (char *)malloc(needleLength);
strncpy(needle, rawNeedle, needleLength);
haystack = strchr(rawHaystack, needle[0]);
int i = haystack - rawHaystack;
BOOL matchesFound = NO;
if (i + needleLength - 1 < strlen(rawHaystack))
{
while (haystack != NULL)
{
if (i + needleLength - 1 < strlen(rawHaystack))
{
char *substr = (char *)malloc(needleLength);
strncpy(substr, haystack, needleLength);
if (strcmp(needle, substr) == 0)
{
printf("%in", i);
matchesFound = YES;
}
free(substr);
substr = NULL;
}
haystack = strchr(haystack+1, needle[0]);
i = haystack - rawHaystack;
}
}
if (matchesFound == NO)
printf("n");
free(needle);
needle = NULL;
}
free(rawNeedle);
free(rawHaystack);
rawNeedle = NULL;
rawHaystack = NULL;
return 0;
}
问题输入和输出规范的转录
输入
输入由许多测试用例组成。每个测试用例由三行组成，包含：
- 针的长度
- 针本身
- 干草堆
指针的长度仅受程序可用内存的限制，因此不要做出任何假设，而是根据需要读取长度并分配内存。干草堆的大小不受限制，这意味着你的程序不应该一次读取整个干草堆。KMP算法是基于流的，也就是说，它逐个字符地处理草堆，所以这不是问题。
测试用例一个接一个地出现，每个用例占用三行，中间没有额外的空间或换行符。
输出
对于每个测试用例，您的程序应该输出大海捞针出现的所有位置。如果找到匹配项，则输出应包含匹配项的第一个字符的位置。草垛中的字符从零开始编号。
对于给定的测试用例，输出的位置应该按升序排序，并且每个位置都应该打印在单独的一行中。对于两个不同的测试用例，位置应该用空行分隔。
为什么要使用任何内存分配？如果规范中包含最大针头长度为10000，只需使用本地阵列：
char needle[RAW_INPUT_SIZE];
char haystack[RAW_INPUT_SIZE];
直接阅读这些内容；不要到处抄。
char *substr = (char *)malloc(needleLength);
strncpy(substr, haystack, needleLength);
if (strcmp(needle, substr) == 0)
目前尚不清楚您的指针长度是否包括尾部零位。因此，这既不能分配足够的空间，也不能保证空终止，这两者都很容易导致SIGABRT问题。
在干草堆上重复使用strlen()会使程序运行缓慢。您可以计算长度，而无需在每根针和草垛上进行多次strlen()。
除非保证数据中没有空格，否则scanf()代码的读取量将低于预期。您应该始终检查您是否获得了所期望的所有值。
您应该查找函数strstr()。
我不确定这是否是问题的直接原因，但一个明显的问题是您没有正确使用strncpy。CCD_ 8不一定是NUL终止的。
此外，您不会检查malloc是否成功，也不会检查strchr是否成功。
您可能正在覆盖关键内存。
指针的长度仅受程序可用内存的限制，因此不要做出任何假设，而是根据需要读取长度并分配内存。干草堆的大小不受限制，这意味着你的程序不应该一次读取整个干草堆。KMP算法是基于流的，也就是说，它逐个字符地处理草堆，所以这不是问题。
您可以指望某些输入的长度超过10000 chars。这意味着您正在使用未分配的内存，其后果是不可预测的。
更可预测的是，正如Jonathan Leffler已经提到的那样，你的substr通常不会以0结尾，所以如果substr后面紧跟着一个"\0"字符，那么strcmp只能返回0，因此你很可能会错过haystack中出现的needle（并且在你的算法过程中可能会遇到麻烦）。
你的算法是幼稚的算法（通过专门扫描needle的第一个字符来增强），可能太慢了：
然而，一个天真的方法可能会超过时间限制，而其他算法则更复杂。。。选择权在你。
您应该为每个测试用例
- 读取针的长度
- 为针分配足够的空间（包括0终止符）
- 读针
- 大海捞针
SPOJ建议使用KMP算法，并非没有理由。使用Boyer-Moore算法是一个很好的选择，但会使处理跨越块边界的匹配变得更加复杂。