0

I've just started learning about divide and conquer and I'm trying to write a program that displays the longest common prefix from a list of strings.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const char *lcpUtil(char str1[], char str2[])
{
    char *result = malloc(sizeof(char) * 100);
    result = "";
    int n1 = strlen(str1), n2 = strlen(str2);
    
    for(int i = 0, j = 0; i <= n1-1 && j <= n2-1; i++, j++)
    {
        if(str1[i] != str2[j])
            break;
        strncat(result, &str1[i], 1); // append the prefix to the result string
    } 
    
    return (result);
}

const char *lcp(char **str, int l, int r)
{
    char str1[100], str2[100];

    if (l < r)
    {
        int m = (l + r)/2;
        
        strcpy(str1, lcp(str, l, r));
        strcpy(str2, lcp(str, m+1, r));
    }

    return (lcpUtil(str1, str2));
}

int main(int argc, char **argv)
{
    char *arr[4] = {"apple", "application", "april", "apartment"}; // ap
    int n = 4;
    char prefix[100];

    strcpy(prefix, lcp(arr, 0 , n-1));

    if(strlen(prefix))
    {
        printf("The longest common prefix: %s\n", prefix);
    }
    else
        printf("There is no common prefix");

    return 0;
}

Right now, I'm getting a segmentation and I'm not certain why.

rmmstn
  • 25
  • 2
  • Not sure what's causing the seg fault, but this code is very leaky. – Fred Larson May 06 '21 at 20:37
  • 1
    Oh, now I know what's causing the seg fault: `result = "";` Everything writing to `result` is undefined behavior. To make `result` an empty string, you could do something as simple as `*result = 0;` – Fred Larson May 06 '21 at 20:39
  • @FredLarson I know one issue is that I didn't free the memory allocated with malloc, but I wanted to first get the program working – rmmstn May 06 '21 at 20:40
  • @FredLarson It gave me some ideas, I didn't initially use dynamic allocation, but I'd get a warning saying: 'function returns address of local variable'. Would strncat work with a dynamically allocated string, or do I have to implement my own version in this case? – rmmstn May 06 '21 at 20:49
  • `strncat()` should be fine. Just make sure your pointer still points to the dynamically allocated buffer, not a string literal. – Fred Larson May 06 '21 at 20:50

1 Answers1

1

You allocated space for your result, pointed the variable result (char*) to that, then you reassigned it to point to a constant string elsewhere from where you allocated. That's clearly not what you intended. As others have commented, this needs a bit of work.

JayC
  • 7,053
  • 2
  • 25
  • 41
  • I intended to signal the fact that the result string is empty before appending the actual prefix there, so that I wouldn't get undefined behavior when appending to result using strncat – rmmstn May 06 '21 at 20:44