-2

I'm trying to write a program that displays the longest common prefix using the divide and conquer method. My code:

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

const char *lcpUtil(char str1[], char str2[])
{
    char *result = NULL;
    result = (char *)malloc(sizeof(char) * 100);

    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)
    {
        return (str[l]);
    }


    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;
}

If I run this, a get a segmentation fault, debugging with gdb says:

Program received signal SIGSEGV, Segmentation fault.
0x00005555555552b7 in lcp (str=<error reading variable: Cannot access memory at address 0x7fffff7fefa8>, l=<error reading variable: Cannot access memory at address 0x7fffff7fefa4>, 
    r=<error reading variable: Cannot access memory at address 0x7fffff7fefa0>) at lab11.c:23
#1  0x0000555555555325 in lcp (str=0x7fffffffde40, l=0, r=3) at lab11.c:30

I know I didn't free the memory allocated with malloc, but it should still be working. I'm not sure why this is happening. Any ideas?

Andrei0408
  • 197
  • 7
  • `for(int i = 0, j = 0; i <= n1-1 && j <= n2-1; i++, j++)` <<- do you think that i and j could differ inside this loop? – wildplasser May 07 '21 at 16:07
  • @wildplasser Well, wouldn't they differ if the strings had different lengths? – Andrei0408 May 07 '21 at 16:12
  • No, the loop will terminate if the end of one of the strings is reached. (and i==j), in any case) – wildplasser May 07 '21 at 16:13
  • @wildplasser But even with 2 indexes, shouldn't the code work fine (not give a seg fault), I mean, I don't see how this would cause the seg fault. Someone said "Also undefined behavior is invoked by using contents of uninitialized buffer allocated via malloc() and assigned to result in strncmp() called from lcpUtil." This is the issue I'm having trouble solving :/ – Andrei0408 May 07 '21 at 16:19
  • You are complicating your problem. BTW: you don't need to malloc() if the caller allocates the result-buffer. The caller will know the size needed. – wildplasser May 07 '21 at 16:26
  • 1
    A very [similar question](https://stackoverflow.com/questions/67425562/segmentation-fault-longest-common-prefix-divide-and-conquer) (with the same code) was asked yesterday. – 1201ProgramAlarm May 07 '21 at 16:28
  • @1201ProgramAlarm Yes, that's where I took the code, but the question wasn't answered and I couldn't figure this out by myself either – Andrei0408 May 07 '21 at 16:30

2 Answers2

1

An infinite recursion is invoked because the function lcp(str, l, r) calls lcp(str, l, r).

Also undefined behavior is invoked by using contents of uninitialized buffer allocated via malloc() and assigned to result in strncmp() called from lcpUtil.

MikeCAT
  • 73,922
  • 11
  • 45
  • 70
  • I've edited the code to get rid of the infinite recursion. Not sure how to solve the 2nd one though, didn't I initialize the buffer with NULL so signal that it's empty? – Andrei0408 May 07 '21 at 16:10
  • The `NULL` is soon overwritten by the pointer to the buffer allocated, so it mean nothing. You have to initialize the allocated buffer, not only the pointer to point at the buffer. – MikeCAT May 07 '21 at 16:22
0
#include <string.h> /* needed for size_t */

size_t lcp_len(char *left, char *right)
{
    /* if the strings differ we are done */
if (*left != *right) return 0; 
    /* if we reached the end of the string(s) we are done) */
if ( !*left ) return 0;

    /* add 1 to the length and compare the next two characters, recursively */
return 1+lcp_len(left+1, right+1);
}

size_t lcp_fetch(char *dest, char *left, char *right)
{
if (*left != *right) { *dest=0; return 0; }
if ( !*left ) { *dest=0; return 0; }

*dest = *left;
return 1+lcp_fetch(dest+1, left+1, right+1);
}

Now let's call it:

#include <stdio.h>
int main(int argc, char **argv)
{
size_t result_len;
char result[100];

if (argc < 3) return 1;

result_len = lcp_fetch(result, argv[1], argv[2] );
printf("%zu:%s\n", result_len, result );

return 0;
}
wildplasser
  • 43,142
  • 8
  • 66
  • 109