Wildcard Pattern Matching | C ++ program to implement wildcard pattern matching algorithm ; Function that matches input str with given wildcard pattern ; empty pattern can only match with empty string ; lookup table for storing results of subproblems ; initialize lookup table to false ; empty pattern can match with empty string ; Only ' * ' can match with empty string ; fill the table in bottom - up fashion ; Two cases if we see a ' * ' a ) We ignore a * aTM character and move to next character in the pattern , i . e . , a * aTM indicates an empty sequence . b ) ' * ' character matches with ith character in input ; Current characters are considered as matching in two cases ( a ) current character of pattern is ' ? ' ( b ) characters actually match ; If characters don 't match ; Driver code ; char pattern [ ] = " ba * * * * * ab " ; char pattern [ ] = " ba * ab " ; char pattern [ ] = " a * ab " ; char pattern [ ] = " a * * * * * ab " ; char pattern [ ] = " * a * * * * * ab " ; char pattern [ ] = " ba * ab * * * * " ; char pattern [ ] = " * * * * " ; char pattern [ ] = " * " ; char pattern [ ] = " aa ? ab " ; char pattern [ ] = " b * b " ; char pattern [ ] = " a * a " ; char pattern [ ] = " baaabab " ; char pattern [ ] = " ? baaabab " ; char pattern [ ] = " * baaaba * " ;
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool strmatch ( char str [ ] , char pattern [ ] , int n , int m ) { if ( m == 0 ) return ( n == 0 ) ; bool lookup [ n + 1 ] [ m + 1 ] ; memset ( lookup , false , sizeof ( lookup ) ) ; lookup [ 0 ] [ 0 ] = true ; for ( int j = 1 ; j <= m ; j ++ ) if ( pattern [ j - 1 ] == ' * ' ) lookup [ 0 ] [ j ] = lookup [ 0 ] [ j - 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { if ( pattern [ j - 1 ] == ' * ' ) lookup [ i ] [ j ] = lookup [ i ] [ j - 1 ] || lookup [ i - 1 ] [ j ] ; else if ( pattern [ j - 1 ] == ' ? ' str [ i - 1 ] == pattern [ j - 1 ] ) lookup [ i ] [ j ] = lookup [ i - 1 ] [ j - 1 ] ; else lookup [ i ] [ j ] = false ; } } return lookup [ n ] [ m ] ; } int main ( ) { char str [ ] = " baaabab " ; char pattern [ ] = " * * * * * ba * * * * * ab " ; if ( strmatch ( str , pattern , strlen ( str ) , strlen ( pattern ) ) ) cout << " Yes " << endl ; else cout << " No " << endl ; return 0 ; }