More optimized solution, find number of substrings in a string. Using C.

Question

Hi All,

So, I have a task to find number of substrings in given string. I can't use any C libraries for doing this task. stringExist can only have 2 strings as a parameters.

My solution is working, but I have a feeling that there should be a more elegant way to do this task. Solution 1: as it turns out, it doesn't work correctly

#include <stdio.h>

int stringExist(char string[], char s2[]);

int main(void){
    char string[] = "strstrASDstrSTRst";
    char s2[] = "str";
    printf("Final result: %i\n",stringExist(string,s2));
    return 0;
}

int stringExist(char string[], char s2[]){
/* I am aware that I can init all this values in one row */
    int count = 0;
    int size = 0;
    int i = 0;
    int temp = 0;
    int result = 0;

    while(s2[size]!='\0'){        
        size++;
    }

    while(string[i]!='\0')
    {        
        if(string[i]==s2[0])
        {
            printf("Found first occurrence\n");
            count=0;            
            while((temp=(string[i]==s2[count]))!=0)
            {            
                count++;                    
                if(size==count){
                    printf("Match\n");
                    result++;                    
                    break;                    
                }
                i++;
            }
        }
        i++;
    }


    return result;
} 

Solution number 2:

So far no errors found.

Did a little bit different string traversal, now I don't increment i in the compare chars loop.

#include <stdio.h>

int stringExist(char string[], char s2[]);

int main(void){
    char string[] = "bobobobojkhhkjjkhbo;klkl;bobo";
    char s2[] = "bobo";
    printf("Final result: %i\n",stringExist(string,s2));
    return 0;
}

int stringExist(char string[], char s2[]){
    int count = 0;
    int size = 0;
    int i = 0;
    int c = 0;
    int temp = 0;
    int result = 0;

    while(s2[size]!='\0'){      
        size++;
    }
    for(i=0;string[i]!='\0';i++){
        if(string[i]==s2[0])
        {
            printf("Found first occurence at %i\n",i);
            count = 0;
            c = i;              

                while((temp=(string[c]==s2[count]))!=0)
                {       
                    printf("Count %i, I %i, current char: %c\n",count, c,string[c]);
                    count++;                    
                    if(size==count){
                        printf("Match\n");
                        result++;                   
                        break;                  
                    }
                    c++;
                }

        }
    }


    return result;
}

Thanks for you suggestions, Vitaly

Answer 1

This feels like a homework question - in which case you should definitely just do it yourself. But, something that you'll probably want to check for that I don't think your code is handling correctly now is this:

How many times does "bobo" appear in the string "bobobo". It should probably be twice and I think your code as is will only count one.

Good luck, Mark.

Answer 2

Well, from an algorithmic point of view, it's not bad. You can make optimizations, but I don't think that's the point (looks like homework!).

You may have a slight issue: in a string like "hahahaha", how many times should "haha" be detected? Twice? Thrice? Your code would see it twice.

From a stylistic point of view, there's certainly room for improvement, but you'll learn that over time, from coding and reading other's code =). Keep at it!

Answer 3

I suggest writing it the way you would if you were allowed to use library functions. Then go back and write your own versions of those library functions that you used. While writing highly optimized versions of the string.h functions may be difficult, writing decent versions of most of them them in C is pretty easy..

Using subroutines (functions) to preform sub-tasks of this problem will help you to keep your code clear and also avoid certain types of problems, such as if you called:

x = stringExist("aaaaa", "aa");

There are 4 occurances of the string "aa" within "aaaaa", but I don't think that your function will find all of them. The reason for this is that as you search through the larger string for occurances of the second you are using the same index for both the beginning of the string and within the string. In fact, it looks like you would get the wrong results for:

x = stringExist("tBatBath", "tBath");

Unless of course, I've misunderstood what the function was supposed to do.

If you were to write your own version of a string prefix comparing function (essentially memcmp or strncmp) then you would have separated the job of matching the length of the string from looking deeper into the string and probably would not have made such a mistake.

If you are worried about squeezing efficiency out of your functions and the overhead of calling functions, don't. First, it's not that bad. Second, just declare them inline or static inline and if you compile with optimization turned on the compiler will most likely generate code as good as it would have without the use of multiple functions.

Answer 4

beat it: (also works for the extra condition)

int stringExist( char *string, char *sub )
{
  int count = 0;

  while( *string )
  {
    char *a = string, *b = sub;
    while( *a && *a == *b ) {a++;b++;}
    count += !*b;
    ++string;
  }

  return count;
}