Finding strings inside of other strings in order in C

Question

A question on Stack Overflow recently intrigued me to the point of me implementing the functionality in C. Can you critique this algorithm and tell me what is good and bad about it?

This program will tell you if a string is inside of another string.

For example:

• "elf" would be inside "self"
• "hit" would be inside "chemistry"
• "tim" would not be inside "chemistry"
• "try" would be inside "chemistry"

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

/*
 * const char* const read only
 * const char* is read/write
 */
int find_str_in_str(const char* const base, const char* const sub)
{
        int base_len = strlen(base);
        int sub_len  = strlen(sub);
        char *tmp_sub = NULL;

        /* allocate enough mem for the max string length */
        if(base_len > sub_len) {
                tmp_sub = malloc(base_len + 1);
        }
        else {
                tmp_sub = malloc(sub_len + 1);
        }


        if(NULL == tmp_sub) {
                fprintf(stderr, "Runtime error (malloc)\n");
                exit(1);
        }

        int i = 0;
        int j = 0;

        for(; i < sub_len; i++) {
                for(; j < base_len; j++) {
                        if(base[j] == sub[i]) {
                                tmp_sub[i] = base[j];
                                /* the first occurance was found */
                                break;
                        }
                }
        }

        tmp_sub[i++] = '\0';

        if(0 == strcmp(sub, tmp_sub)) {
                free(tmp_sub);
                return 1;
        } else {
                free(tmp_sub);
                return 0;
        }
}

int main(int argc, char **argv)
{  
        if(argc < 3) {
                fprintf(stderr, "Usage: %s %s %s\n", argv[0], "base", "derived");
                return EXIT_FAILURE;
        }

        fprintf(stdout, "Base :    %s\n", argv[0]);
        fprintf(stdout, "Sub  :    %s\n", argv[1]);

        if(1 == find_str_in_str(argv[1], argv[2])) {
                fprintf(stdout, "Result :    true\n");
        } else {
                fprintf(stdout, "Result :    false\n");
        }

        return EXIT_SUCCESS;
}

Answer 1

Allocating tmp_sub only needs to be the size of sub: if sub is found in base then it will be exactly the same length.

Using this fact, the entire algorithm can be simplified to remove the tmp_sub and calls to strcomp entirely.

In your nested for loops, remove the i loop and continue incrementing j each iteration. Increment i iff sub[i] == base[j]. Then, check i. If i == sub_len return true. If the loop exits (where j is equal to base_len) then return false.

int find_str_in_str(const char* const base, const char* const sub)
{
    int base_len = strlen(base);
    int sub_len  = strlen(sub);
    int i = 0;
    int j = 0;

    for ( ; j < base_len; j++) {
        if (sub[i] == base[j]) i++;
        if (i == sub_len) return 1; // we found all sub chars in order
    }
    return 0; // we reached the end of base without finding all chars
}

Insufficient karma to comment @William Morris I had returned to write nearly what you have provided as a higher performance / more obscure solution as well. If you exchange the body of your for loop for the obscure trick I had mentioned above (but have now move below) you can avoid one more logic branch in your code.

static int find_str_in_str(const char *base, const char *sub)
{
    // Check arguments for empty string
    for (; *base != '\0' && *sub != '\0'; ++base) { 
        sub += (int)(*base == *sub);
    }
    return *sub == '\0';
}

Feel free to edit my answer and remove this lower block if you choose to update your answer.

Answer 2

What is good about it? Well it is nicely formatted. What is bad? Pretty much everything else. Sorry.

It is much easier that you think.

static int find_str_in_str(const char *base, const char *sub)
{
    for (; (*base != '\0') && (*sub != '\0'); ++base) {
        if (*base == *sub) {
            ++sub;
        }
    }
    return *sub == '\0';
}

EDIT: Was that condescending? It wasn't meant to be. Your code takes 48 lines to do what I have done more clearly in 6.

• You don't need to call strlen twice because you can determine where the strings end by looking for \0.

• There is no need to allocate a buffer.

• You don't gain anything by making the parameters const char* const - the second const means that the pointer cannot be modified inside the function. Such modification is not generally a problem and is a common way of advancing through each character in a string.

Answer 3

• I is more usefule to print the predefined error messages strerror(errno) and the error number errno. This makes it easier to identifiy the type error.
• It is also useful to add the filename __FILE__ and linenumber __LINE__ of the statement where the error occurs to the error messages.
• There is a slight difference between return(EXIT_FAILURE) and exit(1) as discussed in https://stackoverflow.com/questions/13667364/exit-failure-vs-exit1
• I prefer to do the error processing always the same way: immediately after the system call:

Example:

if ... 
  system call with error processing
else 
  system call with error processing

instead of

if ... 
  system call
else
  system call
error processing of the system calls

in your situation I would prefer the following more compact

if (NULL==(tmp_sub = malloc((sub_len>base_len:sub_len?base_len)+ 1))) {
  fprintf(stderr, "error %d: %s, in " __FILE__  " line " __LINE__ "\n", errno ,stderror(errno);
  exit(EXIT_FAILURE);
}

• I would write the last block of your function in a more compact way

Example

if(0 == strcmp(sub, tmp_sub)) {
  free(tmp_sub);
  return 1;
} else {
  free(tmp_sub);
  return 0;
}

can be written more compcat

result=(0 == strcmp(sub, tmp_sub));
free(tmp_sub);
return result;

Avoiding the if-else-clause as in the last examples makes it easier to follow the program.