#include <iostream>
#include <string>
using namespace std;
bool match (string p, string s)
{
int i, j, m, n ; bool **d;
m=p.length(); n=s.length();
d=new bool *[m+1] ;
for ( i= 0 ; i<=m;i++) d[i] =new bool [n+1];
d[0][0]= true ;
for ( j= 1 ; j<=n;j++) d[0][j]= false ;
for ( i= 1 ; i<=m;i++)
{
if(p[i-1]=='*') d[i][0] =d[i-1][0];
else d[i][0]= false ;
}
for ( i= 1 ; i<=m;i++)
{
for ( j= 1 ; j<=n;j++)
if(p[i-1]=='*')
d[i][j] = d[i-1][j] || d[i][j-1];
else if(p[i-1]=='?') d[i][j] =d[i-1][j-1];
else d[i][j] =d[i-1][j-1] && p[i-1]==s[j-1];
}
return d[m][n];
}
int main()
{
string y="ABCDEF";
string x="?B*F";
string s="123456";
string p="A*5";
cout<<"模式字符串x:"<<x<<endl<<"待匹配字符串y:"<<y<<endl;
cout<<"y"<<(match(x,y)?"符合":"不符合")<<"x"<<endl<<endl;
cout<<"模式字符串p:"<<p<<endl<<"待匹配字符串s:"<<s<<endl;
cout<<"s"<<(match(p,s)?"符合":"不符合")<<"p"<<endl;
return 0;
}