Q:

# Match a pattern and String without using regular expressions

A string and a pattern are given to you. You have to match the pattern and string without using regular expression.

```    Input:
Test Case T.

T no. of lines with the strings and patterns.

E.g.
3
abcbbabc
aba
Includehelp
aa
GreenRedYellowRed
GRYR

Output:
Print the character with their respectively representation.
```

Example

```    T= 3

Input:
String  : abcbbabc
Pattern: aba

Output:
a →  abc
b →  bb

Input:
String  : Includehelp
Pattern: aa

Output:
Matching not possible.

Input:
String  : GreenRedYellowRed
Pattern: GRYR

Output:
G → Green
R → Red
Y → Yellow```

Match a string with a pattern is a problem of combination and we will solve this problem with the backtracking process.

To solve this problem, we will follow this algorithm,

```match(string ,pattern ,string_pointer,patter_pointer,map,set):
if(string_pointer equals to the null pointer of the string and
pattern_pointer equals to the null pointer of the pattern) Then
return true
end if
if(string_pointer equals to the null pointer of the string or
pattern_pointer equals to the null pointer of the pattern) Then
return false
end if
for i-> string_pointer+1 to string_length
taking a substring of the original from string_pointer to i
if(the substring is not in map)Then
if(pattern is already present in the set) Then
continue
end if
insert the pair of substring and the corresponding pattern into the map
insert the pattern into the set
end if
else if(the substring is already map) Then
if(substring's corresponding pattern is not matched with
the pattern which is at the patter_pointer) Then
continue;
end if
end if
if(call the pattern for string_pointer+1 and patter_pointer+1)
return true;
end for
return false;
```

C++ implementation:

``````#include <bits/stdc++.h>
using namespace std;

bool match(string str, string pat, int str_pos, int pat_pos, map<string, char>& m, set<char>& se)
{
if (str_pos == str.length() && pat_pos == pat.length()) {
return true;
}
if (str_pos >= str.length() || pat_pos == pat.length())
return false;
int flag = 0;
for (int i = str_pos + 1; i <= str.length(); i++) {
string s = str.substr(str_pos, (i - str_pos));
//if the substring is not present in the map
if (m.find(s) == m.end()) {
//if the pattern is already has a string
if (se.find(pat[pat_pos]) != se.end())
continue;
m.insert(make_pair(s, pat[pat_pos]));
se.insert(pat[pat_pos]);
flag = 1;
}
//if the substring is already present into the map
else if (m.find(s) != m.end()) {
//if the corresponding pattern is not match with the current pattern
if (m[s] != pat[pat_pos]) {
continue;
}
}
if (match(str, pat, i, pat_pos + 1, m, se))
return true;
if (flag) {
m.erase(s);
se.erase(pat[pat_pos]);
flag = 0;
}
}
return false;
}

void match_the_pattern(string str, string pat)
{
map<string, char> m;
int str_pos = 0;
int pat_pos = 0;
set<char> s;
if (match(str, pat, str_pos, pat_pos, m, s)) {
map<string, char>::iterator it;
for (it = m.begin(); it != m.end(); it++) {
cout << it->second << " -> " << it->first << endl;
}
}
else {
cout << "Matching not possible" << endl;
}
}

int main()
{
int t;

cout << "Test Case : ";
cin >> t;

while (t--) {
string str, pat;
cout << "Enter the String : ";
cin >> str;
cout << "Enter the pattern : ";
cin >> pat;
match_the_pattern(str, pat);
}

return 0;
}``````

Output

```Test Case : 3
Enter the String : abcbbabc
Enter the pattern : aba
a -> abc
b -> bb
Enter the String : includehelp
Enter the pattern : aa
Matching not possible
Enter the String : GreenRedYellowRed
Enter the pattern : GRYR
G -> Green
R -> Red
Y -> Yellow```