Thread: Longest common prefix divide and conquer - seg fault

I'm trying to write a program that prints the longest common prefix, using divide and conquer, but I'm getting a seg fault and I'm not certain why. I'm guessing it has something to do with the result array in lcpUtil. Any idea how I can fix this?

Code:

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


const char *lcpUtil(char str1[], char str2[])
{
	char *result = 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)
	{
		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;
}

Originally Posted by Sir Galahad

The common prefix length can be computed pretty efficiently without all of those expensive allocations.

Code:

#include "stdlib.h"

size_t common_prefix_s(const char* s1, const char* s2)
{
 size_t r = 0;
 for(;;)
 {
  char a = *s1++;
  char b = *s2++;
  if((!a || !b) || a != b)
   break; 
  ++r; 
 }
 return r;
}

size_t common_prefix_a(const char* a[], size_t n)
{
 if(n-- == 0)
  return 0;
 size_t m = 0;
 for(size_t i = 0; i < n; ++i)
 {
  size_t c = common_prefix_s(a[i], a[i + 1]);
  if(c == 0)
   return 0;
  if(m == 0 || c < m)
   m = c;
 }
 return m;
}

#include "stdio.h"

int main(int argc, char** argv)
{
 puts("Prefix Test");
 printf("Usage: %s [...STRINGS...]\n", *argv++);
 size_t d = common_prefix_a((const char**)argv, argc - 1);
 printf("Matches: %zu\n", d);
 if(d != 0)
 {
  printf("Prefix: ");
  char* s = *argv;
  for(size_t i = 0; i < d; ++i)
   putchar(s[i]);
  putchar('\n');
 }
}

You could then print out the prefix using any of the strings (as shown above), make a copy of it, or whatever.

Yes this works, but does this till use divide and conquer? I'm just learning this method and I can't always recognize it

Originally Posted by Salem

Runaway recursion perhaps?

Code:

#0  0x000000000040077a in lcp (str=<error reading variable: Cannot access memory at address 0x7fffff7fef38>, 
    l=<error reading variable: Cannot access memory at address 0x7fffff7fef34>, r=<error reading variable: Cannot access memory at address 0x7fffff7fef30>) at bar.c:23
#1  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#2  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#3  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#4  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#5  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#6  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#7  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#8  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#9  0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#10 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#11 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#12 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#13 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#14 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#15 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#16 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#17 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#18 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#19 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
#20 0x00000000004007e8 in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:31
/// at least 3000

It's the same parameter when you first call it from main.

Code:

(gdb) bt
#0  lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:24
#1  0x00000000004007ef in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:32
#2  0x00000000004008d6 in main (argc=1, argv=0x7fffffffdf48) at bar.c:48
(gdb) frame 1
#1  0x00000000004007ef in lcp (str=0x7fffffffddd0, l=0, r=3) at bar.c:32
32            strcpy(str1, lcp(str, l, r));
(gdb)

You just call the function recursively, with the same input parameters!

> char *result = malloc(sizeof(char) * 100);
If result[0] isn't \0, then your strncat is off in the weeds trashing memory.

I've tried doing

Code:

char *result = NULL;
result = (char *)malloc(sizeof(char) * 100);

But I'm still facing the same issue when debugging :/

Originally Posted by aghast

In this code (from lcp):

Edit:


On further review, that lcp() function is messed up. You don't handle the case where "if (l < r)" fails. But you do expect your return statement to work even though you haven't initialized the buffers?

I'd suggest moving the return statement into the if() block. Then add a new return statement that handles the l >= r case. Maybe just return the "array[l]" string?

You're right, my lcp() function was the issue, it's working perfectly now, thanks a lot!