Regular Expression Matching

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(n²)

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:

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.