find the count of substring in string

Should already processed parts of the string should be consumed or not?

For example, what's the expect answer for case of searching oo in foooo, 2 or 3?

• If the latter (we allow substring overlapping, and the answer is three), then Joachim Isaksson suggested the right code.

• If we search for distinct substrings (the answer should be two), then see the code below (and online example here):

  char *str = "This is a simple string";
  char *what = "is";
  
  int what_len = strlen(what);
  int count = 0;
  
  char *where = str;
  
  if (what_len) 
      while ((where = strstr(where, what))) {
          where += what_len;
          count++;
      }
  

USE KMP and you can do it in O(n)

int fail[LEN+1];
char s[LEN];
void getfail()
{
    //f[i+1]= max({j|s[i-j+1,i]=s[0,j-1],j!=i+1})
    //the correctness can be proved by induction
    for(int i=0,j=fail[0]=-1;s[i];i++)
    {
        while(j>=0&&s[j]!=s[i]) j=fail[j];
        fail[i+1]=++j;
        if (s[i+1]==s[fail[i+1]]) fail[i+1]=fail[fail[i+1]];//optimizing fail[]
    }
}

int kmp(char *t)// String s is pattern and String t is text!
{
    int cnt=0;
    for(int i=0,j=0;t.s[i];i++)
    {
        while(j>=0&&t.s[i]!=s[j]) j=fail[j];
        if (!s[++j])
        {
            j=fail[j];
            cnt++;
        }
    }
    return cnt;// how many times s appeared in t.
}

You could do something like

int countString(const char *haystack, const char *needle){
    int count = 0;
    const char *tmp = haystack;
    while(tmp = strstr(tmp, needle))
    {
        count++;
        tmp++;
    }
    return count;
}

That is, when you get a result, start searching again at the next position of the string.

strstr() doesn't only work starting from the beginning of a string but from any position.