Given two string, in which one is a pattern (Pattern) and the other is a searching expression. Searching expression contains ‘#’.
The # works in the following way:
- A # matches with one or more characters.
- A # matches all characters before a pattern match is found. For example, if pat = “A#B”, and text is “ACCBB”, then # would match only with “CC” and pattern is considered as not found.
Examples :
Input : str = "ABABABA"
pat = "A#B#A"
Output : yes
Input : str = "ABCCB"
pat = "A#B"
Output : yes
Input : str = "ABCABCCE"
pat = "A#C#"
Output : yes
Input : str = "ABCABCCE"
pat = "A#C"
Output : no
We can observe that whenever we encounter ‘#’, we have to consider as many characters till the next character of the pattern will not be equal to the current character of the given string. Firstly, we check if the current character of the pattern is equal to ‘#’-
a) If not then we check whether the current character of string and pattern are the same or not, if same, then increment both counters else return false from here only. No need for further checking.
b) If yes, then we have to find the position of a character in the text that matches with the next character of the pattern.
C++
// C++ program for pattern matching // where a single special character // can match one more characters#include<bits/stdc++.h>using namespace std;// Returns true if pat matches with textint regexMatch(string text, string pat){ int lenText = text.length(); int letPat = pat.length(); // i is used as an index in pattern // and j as an index in text int i = 0, j = 0; // Traverse through pattern while (i < letPat) { // If current character of // pattern is not '#' if (pat[i] != '#') { // If does not match with text if (pat[i] != text[j]) return false; // If matches, increment i and j i++; j++; } // Current character is '#' else { // At least one character // must match with # j++; // Match characters with # until // a matching character is found. while (text[j] != pat[i + 1]) j++; // Matching with # is over, // move ahead in pattern i++; } } return (j == lenText);}// Driver codeint main(){ string str = "ABABABA"; string pat = "A#B#A"; if (regexMatch(str, pat)) cout << "yes"; else cout << "no"; return 0;} |
Java
// Java program for pattern matching // where a single special character // can match one more charactersimport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Returns true if pat // matches with text. public static boolean regexMatch (String text, String pat) { int lenText = text.length(); int lenPat = pat.length(); char[] Text = text.toCharArray(); char[] Pat = pat.toCharArray(); // i is used as an index in pattern // and j as an index in text. int i = 0, j = 0; // Traverse through pattern while (i < lenPat) { // If current character of // pattern is not '#' if (Pat[i] != '#') { // If does not match with text. if (Pat[i] != Text[j]) return false; // If matches, increment i and j i++; j++; } // Current character is '#' else { // At least one character // must match with # j++; // Match characters with # until // a matching character is found. while (Text[j] != Pat[i + 1]) j++; // Matching with # is over, // move ahead in pattern i++; } } return (j == lenText); } // Driver code public static void main (String[] args) { String str = "ABABABA"; String pat = "A#B#A"; if (regexMatch(str, pat)) System.out.println("yes"); else System.out.println("no"); }}// This code is contributed by Mr. Somesh Awasthi |
Python3
# Python3 program for pattern matching# where a single special character# can match one more characters# Returns true if pat matches with# textdef regexMatch(text, pat): lenText = len(text) letPat = len(pat) # i is used as an index in # pattern and j as an index # in text i = 0 j = 0 # Traverse through pattern while (i < letPat): # If current character of # pattern is not '#' if (pat[i] != '#'): # If does not match with # text if (pat[i] != text[j]): return False # If matches, increment # i and j i += 1 j += 1 # Current character is '#' else: # At least one character # must match with # j += 1 # Match characters with # until # a matching character is found. while (text[j] != pat[i + 1]): j += 1 # Matching with # is over, # move ahead in pattern i += 1 return (j == lenText)# Driver codeif __name__ == "__main__": st = "ABABABA" pat = "A#B#A" if (regexMatch(st, pat)): print("yes") else: print("no")# This code is contributed by Chitranayal |
C#
// C# program for pattern matching // where a single special character // can match one more charactersusing System;class GFG{ // Returns true if pat // matches with text. public static bool regexMatch (String text, String pat) { int lenText = text.Length; int lenPat = pat.Length; char []Text = text.ToCharArray(); char []Pat = pat.ToCharArray(); // i is used as an index in pattern // and j as an index in text. int i = 0, j = 0; // Traverse through pattern while (i < lenPat) { // If current character // of pattern is not '#' if (Pat[i] != '#') { // If does not match with text. if (Pat[i] != Text[j]) return false; // If matches, increment i and j i++; j++; } // Current character is '#' else { // At least one character // must match with # j++; // Match characters with # until // a matching character is found. while (Text[j] != Pat[i + 1]) j++; // Matching with # is over, // move ahead in pattern i++; } } return (j == lenText); } // Driver code public static void Main () { String str = "ABABABA"; String pat = "A#B#A"; if (regexMatch(str, pat)) Console.Write("yes"); else Console.Write("no"); }}// This code is contributed by nitin mittal |
PHP
<?php// PHP program for pattern matching // where a single special character // can match one more characters// Returns true if pat// matches with textfunction regexMatch($text, $pat){ $lenText = strlen($text); $letPat = strlen($pat); // i is used as an index in pattern // and j as an index in text $i = 0; $j = 0; // Traverse through pattern while ($i < $letPat) { // If current character of // pattern is not '#' if ($pat[$i] != '#') { // If does not match with text if ($pat[$i] != $text[$j]) return false; // If matches, increment i and j $i++; $j++; } // Current character is '#' else { // At least one character // must match with # $j++; // Match characters with # until // a matching character is found. while ($text[$j] != $pat[$i + 1]) $j++; // Matching with # is over, // move ahead in pattern $i++; } } return ($j == $lenText);}// Driver code$str = "ABABABA";$pat = "A#B#A";if (regexMatch($str, $pat)) echo "yes";else echo "no";// This code is contributed by nitin mittal?> |
Javascript
<script>// Javascript program for pattern matching// where a single special character// can match one more characters // Returns true if pat // matches with text. function regexMatch(text,pat) { let lenText = text.length; let lenPat = pat.length; let Text = text.split(""); let Pat = pat.split(""); let i = 0, j = 0; // Traverse through pattern while (i < lenPat) { // If current character of // pattern is not '#' if (Pat[i] != '#') { // If does not match with text. if (Pat[i] != Text[j]) return false; // If matches, increment i and j i++; j++; } // Current character is '#' else { // At least one character // must match with # j++; // Match characters with # until // a matching character is found. while (Text[j] != Pat[i + 1]) j++; // Matching with # is over, // move ahead in pattern i++; } } return (j == lenText); } // Driver code let str = "ABABABA"; let pat = "A#B#A"; if (regexMatch(str, pat)) document.write("yes"); else document.write("no"); // This code is contributed by rag2127</script> |
Output:
yes
This article is contributed by Roshni Agarwal. If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
