Substring Pattern Frequency — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Substring Pattern Frequency problem optimally.
O(|S|+|P|)O(|P|)Problem Description
Given two strings S and P, where S is the text and P is a non‑empty pattern, compute the number of times P appears in S. Overlapping occurrences are counted separately; for example, in "aaaa" the pattern "aa" occurs three times (positions 0‑1, 1‑2, and 2‑3). The algorithm must run in O(|S|+|P|) time and O(|P|) auxiliary space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Substring Pattern Frequency"
WHY DOES IT MATTER?
The substring pattern frequency problem is essential in various applications, such as text search, data compression, and bioinformatics.
OPTIMIZATION CHALLENGE
The key insight that reduces time complexity is the use of a prefix array to skip unnecessary characters in the text S.
REAL-WORLD CONNECTION
In distributed systems, efficient string matching algorithms like KMP are crucial for tasks like log analysis, data filtering, and content search.
When implementing the KMP algorithm, ensure that the prefix array is correctly computed and used to skip characters in the text S.
COMPLEXITY AT A GLANCE
O(|S|+|P|)O(|P|)Core Theory — Why This Approach?
The KMP algorithm is based on the concept of prefix and suffix arrays. The prefix array π(i) is defined as the length of the longest proper prefix of P[0..i] that is also a suffix. The algorithm preprocesses the pattern P to create this prefix array, which is then used to search for the pattern in the text S.
The naive approach fails on large inputs because it has a time complexity of O(|S| * |P|). The KMP algorithm optimizes this by using the prefix array to skip unnecessary characters in the text S, achieving a time complexity of O(|S|+|P|).
The KMP algorithm is an example of a string matching algorithm that uses dynamic programming to preprocess the pattern and achieve efficient searching.
Interview Questions on This Problem
Q1Given two strings S and P, find the number of occurrences of P in S, where overlapping occurrences are counted separately.
Use the KMP algorithm to preprocess the pattern P and create a prefix array. Then, iterate over the text S and use the prefix array to skip unnecessary characters and count the occurrences of P.
Q2How would you optimize the string matching algorithm to achieve a time complexity of O(|S|+|P|)?
By using the KMP algorithm, which preprocesses the pattern P to create a prefix array that helps skip unnecessary characters in the text S.
Q3What is the purpose of the prefix array in the KMP algorithm?
The prefix array π(i) stores the length of the longest proper prefix of P[0..i] that is also a suffix. It helps in skipping unnecessary characters in the text S while searching for the pattern P.
Examples
Input
S = "ababa", P = "aba"
Output
2
Explanation: The pattern "aba" starts at index 0 ("aba"ba) and at index 2 (ab"aba"). Both occurrences are counted.
Input
S = "aaaaa", P = "aa"
Output
4
Explanation: Positions 0‑1, 1‑2, 2‑3, and 3‑4 each contain "aa", giving four overlapping matches.
Input
S = "xyz", P = "xyzz"
Output
0
Explanation: The pattern is longer than the text, so no occurrence exists.
Constraints
- 1 <= |S| <= 10^5
- 1 <= |P| <= 10^4
- S and P consist of lowercase English letters only
Optimal Approach & Strategy
The optimized approach uses the KMP algorithm to preprocess the pattern P and create a prefix array, achieving a time complexity of O(|S|+|P|).
Brute Force Approach
A brute force approach would involve iterating over the text S and checking if the current substring matches the pattern P, resulting in a time complexity of O(|S| * |P|).
Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trimEnd().split('\n');
const S = input[0]||'';
const P = input[1]||'';
function prefixFunction(p){
const m=p.length;
const pi=new Array(m).fill(0);
for(let i=1;i<m;i++){
let j=pi[i-1];
while(j>0 && p[i]!==p[j]) j=pi[j-1];
if(p[i]===p[j]) j++;
pi[i]=j;
}
return pi;
}
function countPattern(S,P){
if(P.length===0) return 0;
const pi=prefixFunction(P);
let cnt=0, j=0;
for(let i=0;i<S.length;i++){
while(j>0 && S[i]!==P[j]) j=pi[j-1];
if(S[i]===P[j]) j++;
if(j===P.length){
cnt++;
j=pi[j-1];
}
}
return cnt;
}
console.log(countPattern(S,P).toString());#include <bits/stdc++.h>
using namespace std;
static vector<int> prefix_function(const string& p){
int m=p.size();
vector<int> pi(m,0);
for(int i=1;i<m;++i){
int j=pi[i-1];
while(j>0 && p[i]!=p[j]) j=pi[j-1];
if(p[i]==p[j]) ++j;
pi[i]=j;
}
return pi;
}
int countPattern(const string& S, const string& P){
if(P.empty()) return 0;
int n=S.size(), m=P.size();
vector<int> pi=prefix_function(P);
int cnt=0, j=0;
for(int i=0;i<n;++i){
while(j>0 && S[i]!=P[j]) j=pi[j-1];
if(S[i]==P[j]) ++j;
if(j==m){
++cnt;
j=pi[j-1]; // allow overlapping
}
}
return cnt;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string S,P;
getline(cin,S);
getline(cin,P);
cout<<countPattern(S,P)<<"\n";
return 0;
}import java.io.*;
public class Main {
private static int[] prefixFunction(String p){
int m=p.length();
int[] pi=new int[m];
for(int i=1;i<m;i++){
int j=pi[i-1];
while(j>0 && p.charAt(i)!=p.charAt(j)) j=pi[j-1];
if(p.charAt(i)==p.charAt(j)) j++;
pi[i]=j;
}
return pi;
}
public static int countPattern(String S, String P){
if(P.isEmpty()) return 0;
int n=S.length(), m=P.length();
int[] pi=prefixFunction(P);
int cnt=0, j=0;
for(int i=0;i<n;i++){
while(j>0 && S.charAt(i)!=P.charAt(j)) j=pi[j-1];
if(S.charAt(i)==P.charAt(j)) j++;
if(j==m){
cnt++;
j=pi[j-1];
}
}
return cnt;
}
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String S=br.readLine();
String P=br.readLine();
if(S==null) S="";
if(P==null) P="";
System.out.println(countPattern(S,P));
}
}import sys
def prefix_function(p: str):
m=len(p)
pi=[0]*m
for i in range(1,m):
j=pi[i-1]
while j>0 and p[i]!=p[j]:
j=pi[j-1]
if p[i]==p[j]:
j+=1
pi[i]=j
return pi
def count_pattern(S: str, P: str) -> int:
if not P:
return 0
pi=prefix_function(P)
cnt=0
j=0
for ch in S:
while j>0 and ch!=P[j]:
j=pi[j-1]
if ch==P[j]:
j+=1
if j==len(P):
cnt+=1
j=pi[j-1]
return cnt
def main():
data=sys.stdin.read().splitlines()
S=data[0] if len(data)>0 else ''
P=data[1] if len(data)>1 else ''
print(count_pattern(S,P))
if __name__=='__main__':
main()const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trimEnd().split('\n');
const S = input[0]||'';
const P = input[1]||'';
function prefixFunction(p){
const m=p.length;
const pi=new Array(m).fill(0);
for(let i=1;i<m;i++){
let j=pi[i-1];
while(j>0 && p[i]!==p[j]) j=pi[j-1];
if(p[i]===p[j]) j++;
pi[i]=j;
}
return pi;
}
function countPattern(S,P){
if(P.length===0) return 0;
const pi=prefixFunction(P);
let cnt=0, j=0;
for(let i=0;i<S.length;i++){
while(j>0 && S[i]!==P[j]) j=pi[j-1];
if(S[i]===P[j]) j++;
if(j===P.length){
cnt++;
j=pi[j-1];
}
}
return cnt;
}
console.log(countPattern(S,P).toString());Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.