Thread: Longest common prefix divide and conquer - seg fault

  1. #1
    Registered User
    Join Date
    Oct 2020
    Posts
    69

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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,625
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    240
    Quote Originally Posted by rmmstn View Post
    I'm trying to write a program that prints the longest common prefix
    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.

  4. #4
    Registered User
    Join Date
    Oct 2020
    Posts
    69
    Quote Originally Posted by Sir Galahad View Post
    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

  5. #5
    Registered User
    Join Date
    Oct 2020
    Posts
    69
    Quote Originally Posted by Salem View Post
    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 :/

  6. #6
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    240
    Quote Originally Posted by rmmstn View Post
    Yes this works, but does this till use divide and conquer? I'm just learning this method and I can't always recognize it
    No, divide and conquer implies recursion. This would be the "iterative approach".

  7. #7
    Registered User
    Join Date
    Apr 2021
    Posts
    34
    In this code (from lcp):

    int m = (l + r)/2;

    strcpy(str1, lcp(str, l, r));
    strcpy(str2, lcp(str, m+1, r));

    I think the first strcpy line should be "lcp(str, l, m)" instead of "..., l, r)".

    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?
    Last edited by aghast; 05-07-2021 at 12:12 PM. Reason: Add more content

  8. #8
    Registered User
    Join Date
    Oct 2020
    Posts
    69
    Quote Originally Posted by aghast View Post
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Divide & conquer find min and max by recurse
    By Siggi in forum C Programming
    Replies: 9
    Last Post: 03-21-2015, 07:56 AM
  2. Replies: 8
    Last Post: 03-26-2012, 03:46 PM
  3. Divide and Conquer Merge_sort
    By nimitzhunter in forum C++ Programming
    Replies: 4
    Last Post: 12-10-2010, 06:39 PM
  4. Divide and Conquer: array in the reverse order
    By Steamer in forum C Programming
    Replies: 11
    Last Post: 03-08-2004, 07:31 PM
  5. divide and conquer
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 06-13-2002, 09:52 AM

Tags for this Thread