Я написал эту небольшую программу, чтобы найти все вхождения подстроки в большую строку или иглу в стоге сена . Когда я запускаю программу локально, она работает нормально. Однако, когда я отправляю его на онлайн-конкурс на судейство, он выдает ошибку SIGBART. Я предположил, что это из-за плохого управления памятью, поэтому я удалил вызовы функций free(), но затем я получил ошибку Time Limit Exceeded (но ошибка 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("%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
Входные данные состоят из нескольких контрольных примеров. Каждый тестовый набор состоит из трех строк, содержащих:
- длина иглы,
- сама игла,
- стог сена.
Длина иглы ограничена только объемом памяти, доступной вашей программе, поэтому не делайте никаких предположений - вместо этого считывайте длину и выделяйте память по мере необходимости. Стог сена не ограничен по размеру, что означает, что ваша программа не должна читать весь стог сена сразу. Алгоритм KMP основан на потоке, т. Е. Обрабатывает стог сена символ за символом, поэтому это не проблема.
Контрольные примеры выполняются один за другим, каждая занимает три строки, без дополнительного пробела или разрывов между ними.
выход
Для каждого тестового случая ваша программа должна выводить все положения вхождений иглы в стоге сена. Если совпадение найдено, выходные данные должны содержать позицию первого символа совпадения. Символы в стоге сена нумеруются, начиная с нуля.
Для данного тестового примера выходные позиции должны быть отсортированы в порядке возрастания, и каждая из них должна быть напечатана в отдельной строке. Для двух разных тестовых случаев позиции должны быть разделены пустой строкой.