Count occurences of pattern string in C

Count occurences of pattern string


Level: Medium

Given a source string S and a pattern string P, count the number of times the pattern string P occurs in the source string S.
Note: Overlapping sequences are counted as separate occurrences.

Input Format:
First line is the source string S s.t. 1 <= |S| <= 8192 characters
Second line is the pattern string P s.t. 1 <= |P| <= 8192 characters

Output Format:
Output a single integer containing the number of occurrences of pattern string P in source string S.

InputOutput
Test Case 1
mississippi
issi
2
Test Case 2
ouagadougou
ou
3
Test Case 3
banana
ana
2
Test Case 4
a
banana
0
Test Case 5
ghhana
ha
1

Sample solution (Provided by instructor) :
#include <stdio.h>

/*
 *-----------------------------------------------------------
 * return 1 if s and t are equal, otherwise return 0
 *-----------------------------------------------------------
 */
int string_equals(char s[], char t[])
{
 int i=0;
 while(t[i] != '\0'){
  if (s[i] != t[i]){
   return 0;
  }
  i++;
 }
 return 1;
}
/*
 *---------------------------------------------------------
 * read input from terminal into s, appending a null at the end
 * The end of the input will be either a space, a tab, a newline or EOF
 *---------------------------------------------------------
 */
int read_string(char s[])
{
 int i=0;
 int c = '\0';
 c = getchar();
 while (c!= ' ' && c!='\t' && c!='\n' && c!=-1) {
  s[i] = c;
  i++;
  c = getchar();
 }
 s[i] = '\0';
 return i;
}
int main()
{
 int i;
 char text[8192];
 char pattern[8192];
 int text_length = 0;
 int pattern_length = 0;
 int num_matches = 0;

 for( i=0; i<8192; i++ ) {
  text[i] = '\0';
  pattern[i] = '\0';
 }
 read_string(text);
 read_string(pattern);

 /* Find lengths of the text and the pattern */
 for( i=0 ; text[i] != '\0'; i++ ){
  text_length ++;
 }
 for( i=0; pattern[i] != '\0' ; i++ ){
  pattern_length++;
 }

 /*
  *------------------------------
  * if the string from the current position in the text 
  * matches the pattern, then the number of match is increased by one.
  * Whether there is a match at the current position or not,
  * we should search the next position in the text for the next
  * possibility of a match.
  * This will find overlapping occurrences as well.
  *---------------------------
  */
 for( i=0; i<text_length-pattern_length+1; i++) {
  if(string_equals(text+i,pattern)) {
   num_matches++;
  }
 }

 printf("%d\n",num_matches);
 return 0;
}

Labels: , ,