How to find the number of occurrences of substring in a string?

Question

I wrote this C code that can find the number of occurrences of a substring in a string. The problem is it overlaps meaning if I search for the letters pp in a string that has ppp the answer will be 2 occurrences instead of 1. I need help stopping this overlapping.

Description:
• This command should search for the given substring in string and then
return the number of occurrences of this substring if found or zero if not
found.
• <string> is sample statement
• <substring> contains a character or more that we need to find the number
of its occurrences in <string>
Notes:
• The given string contains multiple words separated by underscore; i.e. the
underscore acts here exactly as if spaces exist between words
• The substring is not necessary be exist in the given string and in this case
return 0

The test cases it has to pass are:

hello_world➔ld ➔ 1 
hello_world➔l ➔ 3 
hello_world_o_w➔o_w ➔ 2 
hellohellohellohello➔lo ➔ 4 
operating_systems➔ss ➔ 0 
defenselessness➔ss ➔ 2 
ppppppp➔pp ➔ 3

char* fullString = arguments[1];
    char* subString = arguments[2];
    int fullLength=strlen(fullString);
    int subLength=strlen(subString);
    int result = 0;

    for(int i=0;i<fullLength;i++){
        int check;
        for(check=0;check<subLength;check++)
            if (fullString[i+check]!=subString[check])
                break;

        if(check==subLength){
            result++;
            check=0;
        }
    }
    return result;

Why you dont simply use strcmp, to check if you have the word pp — Gonçalo Bastos, Nov 18 '20 at 18:38
The string `"ppp"` *do* contain the sub-string `"pp"` twice, so that seems valid to me. What are the requirements and limitations of your assignment or exercise? Please [edit] your question to include the full and complete text for the assignment or exercise (preferably copy-pasted as text). — Some programmer dude, Nov 18 '20 at 18:46
I think [`strstr`](https://en.cppreference.com/w/c/string/byte/strstr) and [`strlen`](https://en.cppreference.com/w/c/string/byte/strlen) with some pointer arithmetic should solve your problem easier than your attempt. And also solve your "overlap" problem. — Some programmer dude, Nov 18 '20 at 18:53
Then that should be included in the assignment, which you should have included in your question. If you don't tell us all the requirements and *all the limitations* it's very hard to help you. With that said, are you allowed to use `strlen`? If not, then it's very easy to implement it yourself (which I recommend, to make your code simpler). I also recommend you create your own `strstr` function, as that will simplify the assignment even further. — Some programmer dude, Nov 18 '20 at 18:58
The only rules are that I can't use strstr however, Im allowed to use strlen — Ammar Montaser, Nov 18 '20 at 19:03
Then I suggest you implement your own `strstr`-like function, perhaps using `strncmp`. Then you could use your own function to find occurrences of the sub-string, increase a counter, step over the sub-string (using `strlen` of the sub-string), and search again from the new position. — Some programmer dude, Nov 18 '20 at 19:07
Solution in JS: https://stackoverflow.com/questions/9493437/highlighting-string-at-multiple-occurrences/72149542#72149542 — Abby, May 07 '22 at 05:13

IrAM · Answer 1 · 2020-11-18T19:23:39.783

This is not a great way or very efficient method, but its simple to understand how it works.

works with the following combinations:

//char shells[] = "ppppppp";
//char repeat[] = "pp";
//char shells[] = "defenselessness";
//char repeat[] = "ss";
//char shells[] = "ppppppp";
//char repeat[] = "ppp";

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

int main(int argc, char *argv[])
{
    char shells[] = "she sells sea shells, but sea shells she sells are not real sea shells";
    char repeat[] = "shells";
    int noccur = 0, i = 0;
    int len = strlen(repeat);
    
    while(shells[i])
    {
        if  (   //length should be more than repeat length, if not we can stop
                ( strlen(shells+i) >= len ) &&
                // iterating only one char at a time
                (!strncmp(shells+i, repeat, len))
            )
        {
           //match occurs we can actually increase the pos(i) with length of repeat word
            i = i+len-1;
            noccur++;
        }
        i++;
    }
    
    printf("%s occured %d times\n", repeat, noccur);
    
    return 0;
}

score 0 · Answer 2 · answered Nov 18 '20 at 19:31

Here is a solution using the function strstr from the standard library:

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

int MatchCount(const char pattern[], const char target[])
{
    int n, patternLength;
    const char *p;

    patternLength = strlen(pattern);
    n = 0;
    if (patternLength > 0) {
        p = strstr(target, pattern);
        while (p != NULL) {
            n++;
            p = strstr(p + patternLength, pattern);
        }
    }
    return n;
}


int main(void)
{
    assert(MatchCount("", "") == 0);
    assert(MatchCount("foo", "") == 0);
    assert(MatchCount("", "foo") == 0);
    assert(MatchCount("foo", "bar") == 0);
    assert(MatchCount("foo", "foo") == 1);
    assert(MatchCount("foo", "foo bar") == 1);
    assert(MatchCount("foo", "bar foo") == 1);
    assert(MatchCount("foo", "foo bar foo") == 2);
    assert(MatchCount("foo", "bar foo foo") == 2);
    assert(MatchCount("pp", "ppp") == 1);
    assert(MatchCount("pp", "pppp") == 2);
    return 0;
}

How to find the number of occurrences of substring in a string?

2 Answers2