Possibility to write code without include <string.h>

onix012 0
Viewed 106

I have written a code that defines a function with signature and takes 2 parameters C, it returns a number from 0 of 1st parameter - If the 2nd parameter contains the 1st parameter or - 1.

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

int str_find(char* needle, char* haystack) {
    int needle_length = strlen(needle);
    int haystack_length = strlen(haystack);

    if (needle_length == 0) {
        return 0;
    }

    if (haystack_length == 0) {
        return -1;
    }

    int par_1 = 0;

    for(int par_2 = 0; par_2 < haystack_length; par_2++) {
        if (haystack[par_2] == needle[0]) {
            for (par_1 = 0; par_1 < needle_length; par_1++)
                if (haystack[par_2 + par_1])
                    break;
            if (par_2 == needle_length)
                return par_2;
        }
    }

    return -1;
}

int main()
{
    printf("%d\n",str_find("=","-h=123"));
    return 0;
}

Would it be possible/How to write this code without using the <string.h> library?

c
3 Answers

If the haystack is a few Gb, why traverse it simply to determine the upper bound? Traverse the haystack only once (or less)...

Little challenges are a good chance to play with code:

#include <stdio.h>

int str_find( char* needle, char* haystack) {
    size_t i = 0, matched = 0;

    while( haystack[ i ] && needle[matched] )
        if( needle[ matched ] == haystack[i] )
            matched++, i++;
        else if( matched )
            i -= matched - 1, matched = 0; // rewind a bit and try again
        else i++;

    return needle[matched] == '\0' ? i - matched : -1;
}

int main() {

    char *hay = "longlongagoinagalaxyfarfarawaygeorgelucasmadeababananana";

    char *needles[] = { "far", "lucas", "yoda", "force", "banana" };

    for( int i = 0; i < sizeof needles/sizeof needles[0]; i++ )
        printf( "%s - %sfound\n", needles[i], str_find( needles[i], hay ) < 0 ? "not " : "" );

    return 0;
}

Output

far - found
lucas - found
yoda - not found
force - not found
banana - found

EDIT:

In fact, rather than simply found/not-found, this challenge suggests finding multiple instances of any needle (or not finding any) so is worthy of more development.

Here, the return from str_find() is put to more use and the testing done by main() made a bit more elaborate.

This code does not prevent searching for a zero length needle. If someone can describe what a zero-length needle looks like, I would appreciate reading about it in the comments.

#include <stdio.h>

char *str_find( char *needle, char *haystack ) {
    size_t i = 0, matched = 0;

    while( needle[ matched ] && haystack[ i ] )
        if( needle[ matched ] == haystack[i] )
            matched++, i++;
        else if( matched )
            i -= matched - 1, matched = 0; // rewind a bit and try again
        else i++;

    return needle[ matched ] ? NULL : haystack + i - matched;
}

int main() {

    char *hay = "longlongagoinagalaxyfarfarawaygeorgelucasmadeababananana";

    char *needles[] = { "long", "far", "lucas", "yoda", "force", "banana", "nananana" };

    for( size_t i = 0; i < sizeof needles/sizeof needles[0]; i++ ) {
        printf( "%s:\n", needles[i] );
        size_t count = 0;
        for( char *p = hay; ( p = str_find( needles[i], p ) ) != NULL; p++ )
            printf( "\t#%d '%-.10s'\n", ++count, p );

        printf( "%d instances\n", count );
    }

    return 0;
}

Output showing the 'needle' and a few more characters of "context" following the needle.

long:
        #1 'longlongag'
        #2 'longagoina'
2 instances
far:
        #1 'farfaraway'
        #2 'farawaygeo'
2 instances
lucas:
        #1 'lucasmadea'
1 instances
yoda:
0 instances
force:
0 instances
banana:
        #1 'bananana'
1 instances
nananana:
0 instances
Fe2O30

You could re-write this function to not use strlen. First you use the results to see if the strings are 0 length, but you can do that by just checking if the first character is 0.

Later you use the length to check the ending of your for loop. Once again you could just check the string at that point to see if it is 0.

In this way you would not have to use the string library.

Hogan0

Would it be possible/How to write this code without using the <string.h> library?

Yes, it is possible.

Current code has problems/weaknesses:

int vs. size_t

For big strings, the length may exceed int. Function goal does want to rerun a -1 under some cases, Better to use a signed integer that encompasses at least 1/2 the size_t range like long or long long or best: ptrdiff_t from <stddef.h>.

const

As the strings are not modified, use const char * parameters to allow for wider use.

Doubtful functionality

if (haystack[par_2 + par_1]) break; simple breaks the loop if not the null character. No matching done.

Efficiency

OP's code appears to use a O(needle_length*haystack_length) approach. O(needle_length + haystack_length) algorithms exist.

int haystack_length = strlen(haystack); not really needed to traverse the entire haystack before the real searching gets started.

Consider testing for the null character instead.

// for(int par_2 = 0; par_2 < haystack_length; par_2++) 
for(int par_2 = 0; haystack[par_2]; par_2++)

int needle_length = strlen(needle); not needed either. Stop comparing when needle[par_1] == 0

Consider

// int str_find( char* needle, char* haystack) 
ptrdiff_t str_find(const char* needle, const char* haystack)

At least code has good parameter names str_find(char* needle, char* haystack).

chux - Reinstate Monica0
Related