Search the pattern in given String
Given two strings, text and pattern, of size N and M (N > M)respectively, the task is to print all occurrences of pattern in text.
Examples:
Input: text = “This is a dummy text”, pattern = “This”
Output: Pattern found at indices: 0
Explanation: The pattern “This” starts from index 0 in the given text.Input: text = “Welcome to Beginner for Beginner”, pattern = “Beginner”
Output: Pattern found at indices: 21 11
Explanation: The pattern “Beginner” starts from the 11th and 21st index (considering the white spaces).
Approach: The approach for this problem is based on the following idea:
Find the possible starting indices of all the starting points in the text. Then for all those indices check if their adjacents match with the next elements of the pattern.
The above idea can be implemented using the queue. Follow the steps mentioned below to implement the idea.
- First of all, use a 256 sized array of unordered_set. Traverse through the text and insert every index to the set of the respective character.
C++
for ( int i = 0; i < st.length(); i++) // Insert every index to the hash set using character // ASCII. structured_text[st[i]].insert(i); |
C++
for ( int ind : structured_text[pattern[0]]) q_indices.push(ind); |
- Then traverse through pattern from i = 1 to M-1:
- If the index in structured_text[pattern[i]] is adjacent to any of the characters present in pat[i-1], push it to the queue for next iteration.
- Otherwise, continue checking for other positions.
C++
for ( int i = 1; i < pattern.length(); i++) { char ch = pattern[i]; int q_size = q_indices.size(); /* the queue contains the number of occurrences of the previous character. traverse the queue for q_size times Check the next character of the pattern found or not. */ while (q_size--) { int ind = q_indices.front(); q_indices.pop(); if (structured_text[ch].find(ind + 1) != structured_text[ch].end()) q_indices.push(ind + 1); } } |
Python3
for i in range ( 1 , pat_len): ch = pattern[i] q_size = len (q_indices) ## The queue contains the ## number of occurrences of ## the previous character. ## Traverse the queue for ## q_size times. ## Check the next character of ## the pattern found or not. while q_size > 0 : q_size - = 1 ind = q_indices[ 0 ] q_indices.pop( 0 ) if ((ind + 1 ) in structured_text[ ord (ch)]): q_indices.append(ind + 1 ) # This code is contributed by akashish_. |
- If the whole pattern is found then return those indices.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Using a 256 sized array of // hash sets. unordered_set< int > structured_text[256]; // Function to perform the hashing void StringSearch(string st) { // Structure the text. It will be // helpful in pattern searching for ( int i = 0; i < st.length(); i++) // Insert every index to the // hash set using character ASCII. structured_text[st[i]].insert(i); } // Function to search the pattern void pattern_search(string st, string pattern) { StringSearch(st); // Queue contain the indices queue< int > q_indices; for ( int ind : structured_text[pattern[0]]) q_indices.push(ind); // Pattern length int pat_len = pattern.length(); for ( int i = 1; i < pat_len; i++) { char ch = pattern[i]; int q_size = q_indices.size(); // The queue contains the // number of occurrences of // the previous character. // Traverse the queue for // q_size times. // Check the next character of // the pattern found or not. while (q_size--) { int ind = q_indices.front(); q_indices.pop(); if (structured_text[ch].find(ind + 1) != structured_text[ch].end()) q_indices.push(ind + 1); } } cout << "Pattern found at indexes:" ; while (!q_indices.empty()) { // last_ind is the last index // of the pattern in the text int last_ind = q_indices.front(); q_indices.pop(); cout << " " << last_ind - (pat_len - 1); } cout << endl; } // Driver code int main() { // Passing the Text string text = "Welcome to Beginner for Beginner" ; string pattern = "Beginner" ; // Function call pattern_search(text, pattern); return 0; } |
Python3
# Python program for the above approach: ## Using a 256 sized array of ## hash sets. structured_text = [ set ({}) for _ in range ( 256 )] ## Function to perform the hashing def StringSearch(st): ## Structure the text. It will be ## helpful in pattern searching global structured_text for i in range ( len (st)): ## Insert every index to the ## hash set using character ASCII. structured_text[ ord (st[i])].add(i) ## Function to search the pattern def pattern_search(st, pattern): global structured_text StringSearch(st) ## Queue contain the indices q_indices = [] for ind in structured_text[ ord (pattern[ 0 ])]: q_indices.append(ind) ## Pattern length pat_len = len (pattern); for i in range ( 1 , pat_len): ch = pattern[i] q_size = len (q_indices) ## The queue contains the ## number of occurrences of ## the previous character. ## Traverse the queue for ## q_size times. ## Check the next character of ## the pattern found or not. while q_size > 0 : q_size - = 1 ind = q_indices[ 0 ] q_indices.pop( 0 ) if ((ind + 1 ) in structured_text[ ord (ch)]): q_indices.append(ind + 1 ) print ( "Pattern found at indexes:" , end = "") while len (q_indices) > 0 : ## last_ind is the last index ## of the pattern in the text last_ind = q_indices[ 0 ] q_indices.pop( 0 ) print (" ", last_ind - (pat_len - 1), end=" ") print ("") ## Driver code if __name__ = = '__main__' : ## Passing the Text text = "Welcome to Beginner for Beginner" pattern = "Beginner" ## Function call pattern_search(text, pattern) # This code is contributed by subhamgoyal2014. |
Java
import java.util.HashSet; import java.util.Queue; import java.util.LinkedList; public class PatternSearch { // Using a 256 sized array of hash sets. private HashSet<Integer>[] structuredText = new HashSet[ 256 ]; // Function to perform the hashing public void stringSearch(String st) { // Structure the text. It will be helpful in pattern searching for ( int i = 0 ; i < 256 ; i++) { structuredText[i] = new HashSet<Integer>(); } // Insert every index to the hash set using character ASCII. for ( int i = 0 ; i < st.length(); i++) { structuredText[( int )st.charAt(i)].add(i); } } // Function to search the pattern public void patternSearch(String st, String pattern) { stringSearch(st); // Queue to contain the indices Queue<Integer> qIndices = new LinkedList<Integer>(); for ( int ind : structuredText[( int )pattern.charAt( 0 )]) { qIndices.add(ind); } // Pattern length int patLen = pattern.length(); for ( int i = 1 ; i < patLen; i++) { char ch = pattern.charAt(i); int qSize = qIndices.size(); // The queue contains the number of occurrences of the previous character. // Traverse the queue for q_size times. // Check the next character of the pattern found or not. while (qSize > 0 ) { qSize--; int ind = qIndices.peek(); qIndices.remove(); if (structuredText[( int )ch].contains(ind + 1 )) { qIndices.add(ind + 1 ); } } } System.out.print( "Pattern found at indexes: " ); while (!qIndices.isEmpty()) { // lastInd is the last index of the pattern in the text int lastInd = qIndices.peek(); qIndices.remove(); System.out.print(lastInd - (patLen - 1 ) + " " ); } System.out.println(); } // Driver code public static void main(String[] args) { PatternSearch ps = new PatternSearch(); // Passing the Text String text = "Welcome to Beginner for Beginner" ; String pattern = "Beginner" ; // Function call ps.patternSearch(text, pattern); } } |
C#
using System; using System.Collections.Generic; class GFG { // Using a Dictionary of lists // for structuring the text static Dictionary< char , List< int > > structuredText = new Dictionary< char , List< int > >(); // Function to perform the hashing static void StringSearch( string st) { for ( int i = 0; i < st.Length; i++) { char ch = st[i]; // Add the index to the list // of corresponding character if (structuredText.ContainsKey(ch)) { structuredText[ch].Add(i); } else { structuredText.Add(ch, new List< int >{ i }); } } } // Function to search the pattern static void pattern_search( string st, string pattern) { StringSearch(st); // Queue to contain the indices Queue< int > q_indices = new Queue< int >(); // Add the first index of the // pattern from the text if (structuredText.ContainsKey(pattern[0])) { q_indices = new Queue< int >( structuredText[pattern[0]]); } // Pattern length int pat_len = pattern.Length; for ( int i = 1; i < pat_len; i++) { char ch = pattern[i]; int q_size = q_indices.Count; // Traverse the queue for // q_size times. // Check the next character of // the pattern found or not. while (q_size-- > 0) { int ind = q_indices.Dequeue(); if (structuredText.ContainsKey(ch) && structuredText[ch].Contains(ind + 1)) { q_indices.Enqueue(ind + 1); } } } Console.Write( "Pattern found at indexes:" ); while (q_indices.Count > 0) { // last_ind is the last index // of the pattern in the text int last_ind = q_indices.Dequeue(); Console.Write( " " + (last_ind - (pat_len - 1))); } Console.WriteLine(); } // Driver code static void Main( string [] args) { // Passing the Text string text = "Welcome to Beginner for Beginner" ; string pattern = "Beginner" ; // Function call pattern_search(text, pattern); } } |
Javascript
// Using a 256 sized array of hash sets const structuredText = Array(256).fill().map(() => new Set()); // Function to perform the hashing function stringSearch(st) { // Structure the text. It will be helpful in pattern searching for (let i = 0; i < st.length; i++) { // Insert every index to the hash set using character ASCII structuredText[st.charCodeAt(i)].add(i); } } // Function to search the pattern function patternSearch(st, pattern) { stringSearch(st); // Queue contain the indices const indicesQueue = []; for (const ind of structuredText[pattern.charCodeAt(0)]) { indicesQueue.push(ind); } // Pattern length const patLen = pattern.length; for (let i = 1; i < patLen; i++) { const ch = pattern.charCodeAt(i); let qSize = indicesQueue.length; // The queue contains the number of occurrences of the previous character // Traverse the queue for qSize times // Check the next character of the pattern found or not while (qSize--) { const ind = indicesQueue.shift(); if (structuredText[ch].has(ind + 1)) { indicesQueue.push(ind + 1); } } } console.log( "Pattern found at indexes:" ); while (indicesQueue.length > 0) { // lastInd is the last index of the pattern in the text const lastInd = indicesQueue.shift(); console.log( " " , lastInd - (patLen - 1)); } console.log(); } // Driver code const text = "Welcome to Beginner for Beginner" ; const pattern = "Beginner" ; // Function call patternSearch(text, pattern); |
Pattern found at indexes: 21 11
Time Complexity: O(N * logK), where K is the maximum occurrence of any character
Auxiliary Space: O(d), d represents a 256 sized array of unordered_set