Tutorialspoint.dev

Match Expression where a single special character in pattern can match one or more characters

Given two string, in which one is pattern (Pattern) and other is searching expression. Searching expression contains ‘#’.

The # works in following way:

  1. A # matches with one or more characters.
  2. 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 pattern will not be equal to the current character of given string. Firstly, we check if the current character of pattern is equal to ‘#’-
a) If not then we check whether the current character of string and pattern are 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 text that matches with next character of 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 text
int 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 code
int main()
{
    string str = "ABABABA";
    string pat = "A#B#A";
    if (regexMatch(str, pat))
        cout << "yes";
    else
        cout << "no";
    return 0;
}

/div>

Java

// Java program for pattern matching 
// where a single special character 
// can match one more characters
  
import 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

C#

// C# program for pattern matching 
// where a single special character 
// can match one more characters
using 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 text
function 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
?>


Output:

yes

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter