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

Question

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

This will print out "first occurrence" every time the first char of s2 is found in s1. — egrunin
– egrunin, Commented Oct 18, 2010 at 19:33
You function isn't working. Try 'char string[] = "strstrASDstrSTRststr";' where the answer should be 4. — Dingo
– Dingo, Commented Oct 18, 2010 at 19:58
Thanks Dingo, I found this problem as well =(...I think I'm using wrong approach here...bah I'm out of ideas. — Vitaly
– Vitaly, Commented Oct 18, 2010 at 20:08

user411313 · Accepted Answer · 2010-10-18 20:33:51Z

3

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

edited Oct 18, 2010 at 20:33

answered Oct 18, 2010 at 20:25

user411313

4,00021 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vitaly Over a year ago

d'oh, sorry not that advanced in C. Sysadmin here =)

Vitaly Over a year ago

ok I got it, that's one impressive solution. Are you human? =)

nategoose · Accepted Answer · 2010-10-18 20:05:35Z

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.

Mark Drago · Accepted Answer · 2010-10-18 19:34:27Z

0

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.

answered Oct 18, 2010 at 19:34

Mark Drago

2,06615 silver badges10 bronze badges

Comments

salezica · Accepted Answer · 2010-10-18 19:37:36Z

0

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!

answered Oct 18, 2010 at 19:37

salezica

77.5k29 gold badges113 silver badges168 bronze badges

1 Comment

Vitaly Over a year ago

Yes it is kind of homework, for myself. Your test case just broke my brain. Thanks for showing point of failure, will look further =).

Collectives™ on Stack Overflow

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

4 Answers 4

2 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related