Последовательные строки

Question

Задание: Вам дан массив strarr строк и целое число k. Ваша задача - вернуть первую самую длинную строку, состоящую из k последовательных строк, взятых в массиве.

Пример :

longest_consec(["zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail"], 2) --> "abigailtheta"

Примечание: Последовательные строки следуют одна за другой без перерыва,

Окончательный код (работает):

char *longestConsec(char *strarr[], int n, int k) {
    if (n == 0 || k > n || k <= 0)
        return "";

    int max_len = 0, len, max_length_returned = 0;
    for (int l = 0; l < n; ++l) {
        max_length_returned += (int)strlen(strarr[l]);
    }
    char *max_str = (char *)malloc(sizeof(char) * max_length_returned + 1); // problem was here - not freed (because need to return it)
    char *str_temp = (char *)malloc(sizeof(char) * max_length_returned + 1);

    for (int i = 0; i < n - k + 1; ++i) {
        strcpy(str_temp, strarr[i]);
        for (int j = 1; j < k; ++j) {
            strcat(str_temp, strarr[i + j]);
        }
        len = (int)strlen(str_temp);
        if (max_len < len) {
            max_len = len;
            strcpy(max_str, str_temp);
        }
    }
    free(str_temp);
    return max_str;
}

int main() {
    char *a[] = { "zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail" };
    char *longest = longestConsec(a, 8, 2);
    printf("string: %s\nlength: %d\n", longest, (int)strlen(longest));
    free(longest);
    return 0;
}

Мой код работает нормально, но у меня утечка памяти. Любые идеи, как решить вышеупомянутую проблему?

Редактировать: лучшее решение, которое я нашел, используя индексы (start & nd) для всех, кто интересуется

char *longestConsec(char *strarr[], int n, int k) {
    if ((n == 0) || (k > (int)n) || (k <= 0))
        return "";
    int maxSum = 0, start = 0, nd = 0; // creating indexes
    for (int i = 0; i <= n - k; i++) {
        int sum = 0;
        for (int j = i; j < i + k; j++)
            sum += (int)strlen(strarr[j]);
        if (sum > maxSum) {
            maxSum = sum; start = i; nd = i + k;
        }
    }
    char *longest = malloc(sizeof(char) * maxSum + 1); // have the exact amount to allocate
    longest[0] = '\0'; // The terminating null character in destination is overwritten by the first character of source
    for (int c = start; c < nd; c++)
        strcat(longest, strarr[c]);
    return longest;
}

Answer 1

Ваш код в main все еще не совсем корректен. Вы звоните longestConsec дважды и никогда не освобождаете возвращенную память.

Вам необходимо освободить память, возвращаемую longestConsec:

int main()
{
  char* a[] = { "zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail" };

  char* longest = longestConsec(a, 8, 2);  // call longestConsec only once
  printf("string: %s\nlength: %d\n", longest, (int)strlen(longest));
  free(longest);

  return 0;
}

Обычно говорят: все, что было возвращено на malloc и друзья должны быть освобождены путем вызова на free в какой-то момент.

Отказ от ответственности: Я не проверял, есть ли еще ошибки в longestConsec.

Answer 2

Проблема заключается в двух вызовах malloc(sizeof(strarr)). Переменная strarr является указателем на строку, а не самой строкой, которая не была выделена. Размер strarr достаточен только для того, чтобы содержать один адрес или несколько символов, но обычно не всю строку. Таким образом, вы используете случайную часть памяти для хранения конца вашей строки.

Если вы сохраняете свой код более или менее таким, какой он есть, вам нужно будет знать, как долго будет длиться полученная самая длинная строка. выделив его с malloc(sizeof(char) * max_length_returned).