10/25/2018 - 1:04 PM

Wildcard Pattern Matching

Case 1: The character is ‘*’ Here two cases arise

We can ignore ‘’ character and move to next character in the Pattern. ‘’ character matches with one or more characters in Text. Here we will move to next character in the string. Case 2: The character is ‘?’ We can ignore current character in Text and move to next character in the Pattern and Text.

Case 3: The character is not a wildcard character If current character in Text matches with current character in Pattern, we move to next character in the Pattern and Text. If they do not match, wildcard pattern and Text do not match.

We can use Dynamic Programming to solve this problem – Let T[i][j] is true if first i characters in given string matches the first j characters of pattern.

DP Initialization: // both text and pattern are null T[0][0] = true; // pattern is null T[i][0] = false; // text is null T[0][j] = T[0][j - 1] if pattern[j – 1] is '*'

DP relation : // If current characters match, result is same as // result for lengths minus one. Characters match // in two cases: // a) If pattern character is '?' then it matches
// with any character of text. // b) If current characters in both match if ( pattern[j – 1] == ‘?’) || (pattern[j – 1] == text[i - 1]) T[i][j] = T[i-1][j-1]
// If we encounter ‘’, two choices are possible- // a) We ignore ‘’ character and move to next // character in the pattern, i.e., ‘’ // indicates an empty sequence. // b) '' character matches with ith character in // input else if (pattern[j – 1] == ‘*’) T[i][j] = T[i][j-1] || T[i-1][j]
else // if (pattern[j – 1] != text[i - 1]) T[i][j] = false

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

bool func (string s, string pt, int n, int m) {
    if (m==0)
        return 0;

    bool dp[n+1][m+1]; //to store if first i characters of s can be obtained from
    //first j characters of pt.
    memset (dp, 0, sizeof(dp));
    dp[0][0]= 1;
    for (int j=1; j<m; j++)//when considering s of zero length, it can be obtained
        //only if there are '*' in pt till first j character
        if (pt[j-1]== '*')
            dp[0][j]= dp[0][j-1];

    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (pt[j-1]== '?' || pt[j-1]==s[i-1])
                dp[i][j]= dp[i-1][j-1];
            else if (pt[j-1]== '*')
                dp[i][j]= dp[i-1][j]||dp[i][j-1];
                dp[i][j]= 0;
    return dp[n][m];

int main() {
    string s= "baaabab", pt= "a*ab";
    getline (cin, s);
    getline (cin, pt);
    cout<< func(s,pt, s.length(), pt.length());