I have written the code already, and its pretty much finished, but while testing it, it would sometimes faulter(very rarely), and I cant quite figure out why.(Input three strings into function, function needs to return the longest substring that is in all three strings).
char* findSubstring(char* string1, char* string2, char* string3) {
int pointer = 0;
int length = 1;
char *temp1;
char* temp2;
for (int i = 0; string1[i]; i ) {
for (int j = 0; string2[j]; j ) {
for (int k = 0; string3[k]; k ) {
if (string1[i] == string2[j] && string3[k] == string1[i]) {
if (strspn(&string1[i], string2) > length && strspn(&string1[i], string2) == strspn(&string2[j], string3)) {
length = strspn(&string1[i], strinh2);
pointer = i;
}
}
}
}
}
temp1 = (char*)malloc(length * sizeof(char) 1);
for (int i = 0; i < length; i ) {
temp1[i] = string1[pointer i];
}
temp1[length] = '\0';
return temp1;
}
So this is the function, and again it works most of the time, but here and there it just throws out something random that is nowhere near the expected outcome.So if someone can see what i can improve on i would appreciate it.
Example of the code not working:
Input:
string1: isdbhfjdfklekrumpirisbgozuesbgbzu
string2: rgekrumpirasz954ho8g
string3: juidfg7808h5840870ghghkrumpirizg78jue56780jgeo8579h9krumpir
expected outcome is "krumpir", i get "is".
CodePudding user response：
Two obvious problems:
strspn is wrong for this -- it finds a prefix of its first argument that consists of characters from anywhere in the second argument. So
strspn("abcd", "ecab") == 3even though the strings are completely different. You'll need to write a longest prefix match function (it does not exist in the stdlib.) Something like:int prefix_match(const char *a, const char *b) { int i = 0; while (a[i] && a[i] == b[i]) i; return i; }when comparing string1 with string2 and string3, you require the matches to be the same length, but you should be considering the minimum of the two match lengths. This causes you to not match
krumpir(your expected result) as string1 and string3 both containkrumpiribut string2 does not.
combining those, you end up with a loop like
for (int i = 0; string1[i]; i)
for (int j = 0; string2[j]; j)
for (int k = 0; string3[k]; k) {
int l2 = prefix_match(&string1[i], &string2[j]);
int l3 = prefix_match(&string1[i], &string3[k]);
if (min(l2, l3) > length) {
length = min(l2, l3);
pointer = i; } }
CodePudding user response：
As the passed strings are not changed within the function then the function parameters should be defined with qualifier const as for example
char * findSubstring( const char *s1, const char *s2, const char *s3 );
As for your code then the function strspn does not do what you think.
According to the C STandard (7.23.5.6 The strspn function)
2 The strspn function computes the length of the maximum initial segment of the string pointed to by s1 which consists entirely of characters from the string pointed to by s2.
That means for example if you call
strspn( "ababccab", "cba" );
then the function return the length of the first string though the first string is not equal to the second string.
Using your approach with nested for loops the function can be defined for example the following way as shown in the demonstration program below.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char * findSubstring( const char *s1, const char *s2, const char *s3 )
{
size_t length = 0;
size_t pos = 0;
size_t n1 = strlen( s1 );
size_t n2 = strlen( s2 );
size_t n3 = strlen( s3 );
for (size_t i = 0; i < n1 - length; i)
{
int found = 1;
for (const char *p2 = s2;
found && ( p2 = strchr( p2, s1[i] ) ) != NULL && p2 - s2 < n2 - length;
p2)
{
for (const char *p3 = s3;
found = ( p3 = strchr( p3, s1[i] ) ) != NULL && p3 - s3 < n3 - length;
p3)
{
size_t n = 1;
while (s1[i n] == p2[n] && p2[n] == p3[n]) n;
if (length < n)
{
length = n;
pos = i;
}
}
}
}
char *result = malloc( length 1 );
if ( result ! NULL )
{
for ( size_t i = 0; i < length; i )
{
result[i] = s1[pos i];
}
result[length] = '\0';
}
return result;
}
int main( void )
{
const char *s1 = "isdbhfjdfklekrumpirisbgozuesbgbzu";
const char *s2 = "rgekrumpirasz954ho8g";
const char *s3 = "juidfg7808h5840870ghghkrumpirizg78jue56780jgeo8579h9krumpir";
char *s = findSubstring( s1, s2, s3 );
if ( s ! NULL ) puts( s );
free( s );
return 0;
}
The program output is
krumpir
CodePudding user response：
Here you have a very naive (primitive) function which does it. You may improve it significantly.
char *weirdstrstr(const char *h, const char *n, size_t npos, size_t len)
{
char tmp[len 1];
memcpy(tmp, n npos, len);
tmp[len] = 0;
return strstr(h, tmp);
}
char *maxsubstr(const char *s1, const char *s2, const char *s3)
{
size_t s1index = 0, s1length = 0, flength = 0, fpos = -1;
size_t s1len = strlen(s1);
char *result = NULL;
for(size_t s1pos = 0; s1pos < s1len; s1pos )
{
for(size_t s1chlen = 1; s1chlen < s1len - s1pos; s1chlen )
{
if(weirdstrstr(s2, s1, s1pos, s1chlen) && weirdstrstr(s3, s1, s1pos, s1chlen))
{
if(flength < s1chlen)
{
flength = s1chlen;
fpos = s1pos;
}
}
}
}
if(fpos != -1 && (result = malloc(flength 1)))
{
memcpy(result, s1 fpos, flength);
result[flength] = 0;
}
return result;
}
int main(void)
{
char *s1 = "isdbhfjdfklekrumpirisbgozuesbgbzu";
char *s2 = "rgekrumpirasz954ho8g";
char *s3 = "juidfg7808h5840870ghghkrumpirizg78jue56780jgeo8579h9krumpir";
char *result = maxsubstr(s1, s2, s3);
if(result) printf("Result = '%s'\n", result);
free(result);
}
https://godbolt.org/z/cv1sMP64G
Program stdout
Result = 'krumpir'