Dynamic Programming | Wildcard Pattern Matching | Linear Time and Constant Space | C ++ program to implement wildcard pattern matching algorithm ; Function that matches input text with given wildcard pattern ; empty pattern can only match with empty string . Base Case : ; step - 1 : initialize markers : ; For step - ( 2 , 5 ) ; For step - ( 3 ) ; For step - ( 4 ) ; For step - ( 5 ) ; For step - ( 6 ) ; For step - ( 7 ) ; Final Check ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool strmatch ( char txt [ ] , char pat [ ] , int n , int m ) { if ( m == 0 ) return ( n == 0 ) ; int i = 0 , j = 0 , index_txt = -1 , index_pat = -1 ; while ( i < n ) { if ( j < m && txt [ i ] == pat [ j ] ) { i ++ ; j ++ ; } else if ( j < m && pat [ j ] == ' ? ' ) { i ++ ; j ++ ; } else if ( j < m && pat [ j ] == ' * ' ) { index_txt = i ; index_pat = j ; j ++ ; } else if ( index_pat != -1 ) { j = index_pat + 1 ; i = index_txt + 1 ; index_txt ++ ; } else { return false ; } } while ( j < m && pat [ j ] == ' * ' ) { j ++ ; } if ( j == m ) { return true ; } return false ; } int main ( ) { char str [ ] = " baaabab " ; char pattern [ ] = " * * * * * ba * * * * * ab " ; char pattern [ ] = " ba * * * * * ab " ; char pattern [ ] = " ba * ab " ; char pattern [ ] = " a * ab " ; if ( strmatch ( str , pattern , strlen ( str ) , strlen ( pattern ) ) ) cout << " Yes " << endl ; else cout << " No " << endl ; char pattern2 [ ] = " a * * * * * ab " ; if ( strmatch ( str , pattern2 , strlen ( str ) , strlen ( pattern2 ) ) ) cout << " Yes " << endl ; else cout << " No " << endl ; return 0 ; }