Wildcard String Match

[namelx]

Hi, guys:

I have a c++ program which was used to do the wildcard string match, but i found there is a bug on my algorithm which i can not fix it. Is there anyone who have the interest to help me on this?

This function support * ( as 0 to many chars) and ? ( as 1 char) wildcard.

I found this mis-match string are : Book and *B?k ( since ? represents 1 char only, it should not match, but the program returns the wrong value).

Here is the function:


stringMatch(String str1, String str2){

int slen1 = str1.length();
int slen2 = str2.length();
int i, j, k;

int[][] matchmap = new int[256][256];
for(i = 0; i<256; ++i)
{
for(j = 0; j<256; ++j)
{
matchmap[i][j] = 0;
}
}



int lbound = 0;
int upbound = 0;

for(i = 0; i< slen1; ++i)
{
int bMatched = 0;
int upthis = upbound;
for(j = lbound; j<=upthis ; ++j)
{

if(j < slen2 && (str1.at(i)== str2.at(j) || str2.at(j) == '?'))
{
matchmap[i][j] = 1;
if(0 == bMatched)
{
lbound = j+1;
}
upbound = j+1;
bMatched = 1;
if(i == slen1 - 1)
{
for(k = j+1 ; k < slen2 && '*' == str2.at(k) ; ++k)
{
matchmap[i][k] = 1;
}
}

}
else if( j < slen2 && str2.at(j) == '*')
{
if(0 == bMatched)
{
lbound = j;
}
for(k = i; k< slen1; ++k)
{
matchmap[k][j] = 1;
}
k = j;
while( ++k < slen2 && '*' == str2.at(k))
{
matchmap[i][k] = 1;
}
if(k<slen2 && (str1.at(i) == str2.at(k) || str2.at(k) == '?'))
{
matchmap[i][k] = 1;
upbound = k+1;
if(i == slen1 - 1)
{

for(k = k+1 ; k < slen2 && '*' == str2.at(k) ; ++k)
{
matchmap[i][k] = 1;
}
}
}
else
{
upbound = k;
}

bMatched = 1;

}
}

if(bMatched != 1)
{
return matchmap[i][j];
}
}
return matchmap[slen1-1][slen2-1];
}