• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Regular Expression Matching

December 22, 2017 by Dhaval Dave

You are given a string T which consists of 0’s and 1’s. Now you input two non-empty strings U and V. Then your task is to match the Regular Expression  – U*V with the given string T and find the number of total successful matches.

(NOTE – Here “*” denotes the string of characters of 0 or more length).

Required Knowledge:

String matching algorithm (Preferably KMP)

Time Complexity:

O(n2)

Solution with Regular Expression:

A sequence of symbols and characters expressing a string or pattern to be searched for within a longer piece of text.

According to the definition of  “*” in regular expression, we note that the number of characters between U and V can range from 0 to |T|-(|U|+|V|). Therefore we can find all positions of occurrence of the strings U and V in T then check among the different occurrences which are possible and then count their number.

Now,to find the positions occurrence of a pattern in text we would use a string matching algorithm. Now out of the different string matching algorithms like Rabin-Karp matching, Finite Automata matching, KMP matching, in this case we would be using the KMP matching due of its faster time complexity of O(n) than the others string matching algorithms.

After finding all the positions of occurrences of U and V, we would check whether the pair of indices say ith position for U and jth position for V are possible or not i.e

(i+|U| <= j)

Example for possible and not possible case:Example explaining possible and not-possible case in regular expression matching

Thus if we find a match then increment a count variable which stores the number of occurrences of U*V.

Code

Implemented in C++

#include <bits/stdc++.h>
#define ll int64_t
#define ff first
#define ss second
#define ii pair<int ,int > 
#define MX 1000002 
using namespace std;

string T,U,V;

int pi[2][1000];

void compute_prefix_fn(int i){   

	if(i==0){
		int m=U.length();
		pi[0][0]=0;
		int k=0;
		//cout<<pi[0][0]<<" ";
		for(int q=1;q<m;q++){
			while(k>0 && U[k]!=U[q])
				k=pi[0][k-1];
			if(U[k]==U[q])
				k++;
			pi[0][q]=k;
			//cout<<pi[0][q]<<" ";
		}
	}
	else{
		int m=V.length();
		pi[1][0]=0;
		int k=0;
		for(int q=1;q<m;q++){
			while(k>0 && V[k]!=V[q])
				k=pi[1][k-1];
			if(V[k]==V[q])
				k++;
			pi[1][q]=k;
		}	
	}
}

int main(){

	cin>>T>>U>>V;

	compute_prefix_fn(0);
	compute_prefix_fn(1);

	vector<int > pos_u,pos_v;

	int k=0;
	for(int q=0;q<T.length();q++){
		while(k>0 && U[k]!=T[q])
			k=pi[0][k-1];
		if(U[k]==T[q])
			k++;
		if(k==U.length()){
			pos_u.push_back(q-U.length()+1);
			k=pi[0][k-1];
		}
	}
	k=0;
	for(int q=0;q<T.length();q++){
		while(k>0 && V[k]!=T[q])
			k=pi[1][k-1];
		if(V[k]==T[q])
			k++;
		if(k==V.length()){
			pos_v.push_back(q-V.length()+1);
			k=pi[1][k-1];
		}
	}

	/*for(int i=0;i<pos_v.size();i++)
		cout<<pos_v[i]<<" ";*/
	int count=0;
	for(int i=0;i<pos_u.size();i++){
		for(int j=0;j<pos_v.size();j++){
			if(pos_u[i]+U.length() <= pos_v[j]){
				//cout<<pos_u[i]<<" "<<pos_v[j]<<endl;
				count++;
			}
		}
	}

	cout<<count<<"\n";
	return 0;
}

 

Example:

Input –

110001010000111100011001010011001
110
010

Output –

8

Explanation –

Now let us check the following indices in T (indexing is done from 0) where (i,j) represents (position of occurrence of U,position of occurrence of V) :-
1.(0,4) – As in this case * can be replaced with 0 since (110)0(010)10000111100011001010011001. Thus we get 1100010.
2.(0,6) – As in this case * can be replaced with 001 since (110)001(010)000111100011001010011001. Thus we get 110001010.
3.(0,22) – As in this case * can be replaced with 0010100001111000110 since (110)0010100001111000110(010)10011001. Thus we get 1100010100001111000110010.
4.(0,24) – As in this case * can be replaced with 001010000111100011001 since (110)001010000111100011001(010)011001. Thus we get 110001010000111100011001010.
5.(14,22) – As in this case * can be replaced with 00110 since 11000101000011(110)00110(010)10011001. Thus we get 11000110010.
6.(14,24) – As in this case * can be replaced with 0011001 since 11000101000011(110)0011001(010)011001. Thus we get 1100011001010.
7.(19,22) – As in this case * can be replaced with 0 characters since 1100010100001111000(110)(010)10011001. Thus we get 110010.
8.(19,24) – As in this case * can be replaced with 01 since 1100010100001111000(110)01(010)011001. Thus we get 11001010.

 

This Article is Published by Arnab Ghosh.
If you want to be a content writer with Gohired.in, please write at career@gohired.in or at admin@gohired.in.

Similar Articles

Filed Under: Algorithm, Amazon Interview Question, Interview Questions Tagged With: implementation, kmp matching, string

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Count Possible Decodings of a given Digit Sequence

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Hackerearth : Counting Subarrays

Find the element that appears once others appears thrice

Mirror of Tree

Sequence Finder Dynamic Programming

Stickler thief

LeetCode: Container With Most Water

Python List

Minimum insertions to form a palindrome

Cisco Hiring Event 21st – 22nd Feb 2015

Handle duplicates in Binary Search Tree

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

SAP Off Campus Hiring_ March 2015 Computer Skills

Leetcode: Merge Intervals

Possible sizes of bus to carry n groups of friends

Fibonacci Hashing & Fastest Hashtable

BlueStone E-commerce Interview Experience

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

The greedy coins game Dynamic Programming

Interfaces in C++ (Abstract Classes in C++)

The Magic HackerEarth Nirvana solutions Hiring Challenge

Find next greater number with same set of digits

Binary Tree in Java

Practo Hiring Experience

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Copyright © 2025 · Genesis Framework · WordPress · Log in