c - C 代码中的 SIGBART 与 malloc/free

Question

我编写了这个小程序来查找较大字符串中所有出现的子字符串，或者干草堆中的针。当我在本地运行该程序时，它似乎工作得很好。然而，当我将其提交给在线竞赛进行评审时，它给出了 SIGBART 错误。我认为这是因为内存管理不善，所以我删除了 free() 函数调用，但随后我收到了 Time Limit Exceeded 错误(但 SIGBART 错误消失了) )。删除 free() 调用会减慢程序速度吗？我的程序有没有漏洞？

这是我正在谈论的比赛: Needle in the Haystack

代码如下:

#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("%i\n%s\n%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("%i\n", 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;
}

<小时/>

问题输入和输出规范的转录

Input

The input consists of a number of test cases. Each test case is composed of three lines, containing:

• the length of the needle,
• the needle itself,
• the haystack.

The length of the needle is only limited by the memory available to your program, so do not make any assumptions - instead, read the length and allocate memory as needed. The haystack is not limited in size, which implies that your program should not read the whole haystack at once. The KMP algorithm is stream-based, i.e. it processes the haystack character by character, so this is not a problem.

The test cases come one after another, each occupying three lines, with no additional space or line breaks in between.

Output

For each test case your program should output all positions of the needle's occurences within the haystack. If a match is found, the output should contain the position of the first character of the match. Characters in the haystack are numbered starting with zero.

For a given test case, the positions output should be sorted in ascending order, and each of these should be printed in a separate line. For two different test cases, the positions should be separated by an empty line.

Answer 1

为什么要使用内存分配？如果规范中包含的最大针长度为 10,000，则只需使用本地数组:

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()。