Given a string str of length N and a substring pattern of length M, the task is to find the frequency of occurrences of pattern as a substring in the given string. If pattern is present in the string str, then print “Yes” with the count of its occurrence. Otherwise, print “No”.
Examples:
Input: str = “neveropen”, pattern = “neveropen”
Output: 2
Explanation:
The occurrence of the string “neveropen” in the string “neveropen” is at index 0 and 8.
Therefore, the count is 2.Input: str = “dhimanman”, pattern = “max”
Output: 0
Naive Approach: Refer to the previous post for the simplest approach to solve the problem. Time Complexity: O(N*M)
Auxiliary Space: O(1)
Approach using KMP Algorithm: Refer to the previous post of this article to solve the problem using KMP algorithm. Time Complexity: O(N + M)
Auxiliary Space: O(M)
Approach using Regular Expression: Follow the steps below to solve the problem:
- Form the regular expression of the string pattern using regex() function.
- Create a smatch M using function smatch().
- Check the presence of the string pattern in the string str using function regex_match() as:
regex_search(str, m, c)
where,
str is the given string,
m is smatch,
c is the regular expression of the string pattern.
- In the above steps, if the function regex_match() returns True, then print “Yes” and find the occurrence of the string pattern. Otherwise, print “No”.
- Create a variable numberOfMatches of data type ptrdiff_t to store the count of occurrence.
- Find the numberOfMatches using function regex_iterator() function as:
ptrdiff_t numberOfMatches = std::distance(sregex_iterator(S.begin(), S.end(), c), sregex_iterator())
- Print the count of occurrence in the above steps as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the frequency of// substring in the given string Svoid find_frequency(string S, string pattern){ // Create a regular expression // of the string pattern regex c(pattern); // Determines the matching behavior smatch m; // Use member function on 'm' // regex_search to check if // string X is present in S or not if (regex_search(S, m, c) == true) { cout << "Yes" << "\n"; } else { cout << "No"; } // Count the number of matches ptrdiff_t numberOfMatches = std::distance( sregex_iterator(S.begin(), S.end(), c), sregex_iterator()); // Print the coun of occurrence cout << "Frequency of string " << pattern << " is " << numberOfMatches;}// Driver codeint32_t main(){ // Given string str and pattern string str = "neveropen"; string pattern = "neveropen"; // Function Call find_frequency(str, pattern); return 0;} |
Java
// Java program for the above approachimport java.util.regex.*;class GFG { // Function to find the frequency of // substring in the given string S static void find_frequency(String S, String pattern) { // Create a regular expression // of the string pattern Pattern c = Pattern.compile(pattern); // Determines the matching behavior Matcher m = c.matcher(S); // Use member function on 'm' // find to check if string X // is present in S or not if (m.find()) { System.out.println("Yes"); } else { System.out.println("No"); } // Count the number of matches int numberOfMatches = 0; m.reset(); while (m.find()) { numberOfMatches++; } // Print the count of occurrence System.out.println("Frequency of string " + pattern + " is " + numberOfMatches); } // Driver code public static void main(String[] args) { // Given string str and pattern String str = "neveropen"; String pattern = "neveropen"; // Function Call find_frequency(str, pattern); }}// Contributed by adityasha4x71 |
Python3
# Python program for the above approachimport redef find_frequency(s, pattern): # Create a regular expression # of the string pattern c = re.compile(pattern) # Determines the matching behavior m = c.search(s) # Use member function on 'm' # find to check if string X # is present in S or not if m: print("Yes") else: print("No") # Count the number of matches numberOfMatches = 0 m = c.finditer(s) for match in m: numberOfMatches += 1 # Print the count of occurrence print("Frequency of string " + pattern + " is " + str(numberOfMatches))# Driver codeif __name__ == "__main__": # Given string str and pattern s = "neveropen" pattern = "neveropen" # Function Call find_frequency(s, pattern)# This code is contributed by princekumaras |
C#
// C# program for the above approachusing System;using System.Text.RegularExpressions;class GFG { // Function to find the frequency of // substring in the given string S static void find_frequency(string S, string pattern) { // Create a regular expression // of the string pattern Regex c = new Regex(pattern); // Determines the matching behavior Match m = c.Match(S); // Use member function on 'm' // find to check if string X // is present in S or not if (m.Success) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } // Count the number of matches int numberOfMatches = 0; m = c.Match(S); while (m.Success) { numberOfMatches++; m = m.NextMatch(); } // Print the count of occurrence Console.WriteLine("Frequency of string " + pattern + " is " + numberOfMatches); } // Driver code public static void Main(string[] args) { // Given string str and pattern string str = "neveropen"; string pattern = "neveropen"; // Function Call find_frequency(str, pattern); }}// This code is contribute by rishab |
Javascript
// JavaScript program for the above approachfunction find_frequency(S, pattern) { // Create a regular expression // of the string pattern const c = new RegExp(pattern); // Determines the matching behavior const m = S.match(c); // Use member function on 'm' // find to check if string X // is present in S or not if (m !== null) { console.log("Yes"); } else { console.log("No"); } // Count the number of matches let numberOfMatches = 0; let m2 = c.exec(S); while (m2 != null) { numberOfMatches++; S = S.substr(m2.index + 1); m2 = c.exec(S); } // Print the count of occurrence console.log("Frequency of string " + pattern + " is " + numberOfMatches);}// Driver codeconst str = "neveropen";const pattern = "neveropen";// Function Callfind_frequency(str, pattern);// This code is contribute by phasing17 |
Output:
Yes Frequency of string neveropen is 2
Time Complexity: O(N + M)
Auxiliary Space: O(M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
