Step by Step solution about How to resolve the algorithm Count occurrences of a substring step by step in the C programming language

The C program contains two functions, match and countSubstring, both of which are used to find and count the occurrences of a substring within a given string.

1. match Function:

• Purpose: To find the number of occurrences of a substring within a given string.
• Parameters:
  • s: The input string to be searched.
  • p: The substring to be found within the input string.
  • overlap: A flag indicating whether to count overlapping occurrences.
• Functionality:
  • It iterates through the input string s character by character.
  • For each character, it compares the next l characters (where l is the length of the substring p) with p.
  • If there's a match, it increments the c counter.
  • It then checks the overlap flag. If overlap is 0 (indicating no overlapping occurrences), it skips l - 1 characters in the input string to avoid counting overlapping occurrences. If overlap is 1 (indicating allowed overlapping occurrences), it continues searching from the next character.
  • After iterating through the entire input string, it returns the count c, which represents the number of occurrences of the substring within the input string.
• Example Usage:
  • In the main function, the match function is used to find the number of occurrences of "th" in "the three truths". The output is 2 because "th" appears twice in the input string.
  • Another usage demonstrates how the overlap flag affects the count. The input string "abababababa" is searched for the substring "aba" with both overlap set to 1 and 0. The output shows that with overlapping allowed, the count is 7, while with no overlapping, the count is 3.

2. countSubstring Function:

• Purpose: To count the number of non-overlapping occurrences of a substring within a given string.
• Parameters:
  • str: The input string to be searched.
  • sub: The substring to be found within the input string.
• Functionality:
  • It initializes a variable length to the length of the substring sub and checks if it's 0. If sub is an empty string, the function returns 0.
  • It uses the strstr function to find the first occurrence of sub within str and assigns the result to a pointer.
  • If the result is not NULL (i.e., sub was found), it increments the count variable.
  • It then updates the str pointer to point to the character after the occurrence of sub found in the previous step.
  • It repeats the process of searching for sub within the remaining portion of str until strstr returns NULL, indicating that no more occurrences of sub were found.
• Example Usage:
  • In the main function, the countSubstring function is used to find the number of non-overlapping occurrences of "th" in "the three truths". The output is 2 because "th" appears twice in the input string, and the function counts only non-overlapping occurrences.
  • It also shows examples of counting occurrences of "abab" in "ababababab" and "ab" in "abaabbabbaba*bbab".

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

int match(const char *s, const char *p, int overlap)
{
        int c = 0, l = strlen(p);

        while (*s != '\0') {
                if (strncmp(s++, p, l)) continue;
                if (!overlap) s += l - 1;
                c++;
        }
        return c;
}

int main()
{
        printf("%d\n", match("the three truths", "th", 0));
        printf("overlap:%d\n", match("abababababa", "aba", 1));
        printf("not:    %d\n", match("abababababa", "aba", 0));
        return 0;
}


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

// returns count of non-overlapping occurrences of 'sub' in 'str'
int countSubstring(const char *str, const char *sub)
{
    int length = strlen(sub);
    if (length == 0) return 0;
    int count = 0;
    for (str = strstr(str, sub); str; str = strstr(str + length, sub))
        ++count;
    return count;
}

int main()
{
    printf("%d\n", countSubstring("the three truths", "th"));
    printf("%d\n", countSubstring("ababababab", "abab"));
    printf("%d\n", countSubstring("abaabba*bbaba*bbab", "a*b"));

    return 0;
}