medium
0 views

Non-overlapping Substring Count

Count the number of non-overlapping occurrences of a pattern string within a given text string.

Understand the Problem

Problem Statement

Given two strings S and P representing a text and a pattern, the task is to find the number of non-overlapping occurrences of the pattern P in the text S.

The pattern matching must not allow overlapping matches. For example, in the text "abababa" with pattern "aba", there are two non-overlapping occurrences: one starting at index 0 and another starting at index 4.

Note: Both strings contain only lowercase alphabets.

Constraints

  • 1 ≤ Length of string S ≤ 105
  • 1 ≤ Length of pattern P ≤ 10
  • String S contains only lowercase alphabets (a-z)
  • Pattern P contains only lowercase alphabets (a-z)
  • Pattern length is at most 10 characters (making KMP/advanced algorithms less necessary)

Examples

Example 1
Input
abababa
aba
Output
2
Explanation

The pattern 'aba' occurs at positions 0 and 4 in 'abababa'. These are non-overlapping because the first match ends at index 2 and the second match starts at index 4.

Example 2
Input
techchampcheckin
ch
Output
3
Explanation

The pattern 'ch' occurs at positions 3, 9, and 13 in 'techchampcheckin'. These occurrences don't overlap with each other.

Solution

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

int main() {
    char S[100001];
    char P[11];
    
    fgets(S, sizeof(S), stdin);
    fgets(P, sizeof(P), stdin);
    
    // Remove newlines from fgets
    S[strcspn(S, "\n")] = 0;
    P[strcspn(P, "\n")] = 0;
    
    int count = 0;
    int lenS = strlen(S);
    int lenP = strlen(P);
    
    // Greedy approach: find non-overlapping matches
    int pos = 0;
    while (pos <= lenS - lenP) {
        // Find next occurrence of P starting from pos
        char *found = strstr(S + pos, P);
        if (found == NULL) {
            break;
        }
        
        // Calculate the actual position in S
        int matchPos = found - S;
        count++;
        
        // Move position to after this match to avoid overlapping
        pos = matchPos + lenP;
    }
    
    printf("%d\n", count);
    return 0;
}
Time:O(n*m) in worst case, where n is length of S and m is length of P. However, since m &le; 10, this is effectively O(n).
Space:O(1) - only using a constant amount of extra space for variables
Approach:

The C solution uses the standard library function strstr() to find pattern occurrences:

  • Read both strings S and P using fgets()
  • Remove trailing newlines with strcspn()
  • Initialize counter and string lengths
  • Use a while loop starting from position 0
  • Use strstr(S + pos, P) to find the next occurrence from current position
  • If found, increment counter and move position to matchPos + lenP (right after the match)
  • Continue until no more matches found
  • Print the final count

Visual Explanation

Loading diagram...
All Problems