ワイルドカード文字列マッチングアルゴリズム-C/C++
先日、ある君が私にこんな問題を出してくれた.二つの文字列、一つは普通の文字列、もう一つは*と?ワイルドカード、*は0～複数の任意の文字を表します.任意の文字を表し、ワイルドカードが複数回表示される場合があります.2つの文字列が等しいかどうかを比較するアルゴリズムを書きます.私は4時間かけて2つのアルゴリズムを書いてこの問題を解決して、簡単にテストして、使いやすいです!
// ， ? *，
char strMatch( const char *str1, const char *str2)
{
int slen1 = strlen(str1);
int slen2 = strlen(str2);
// strl
char matchmap[128][128];
memset(matchmap, 0, 128*128);
matchmap[0][0] = 1;
int i, j, k;
//
for(i = 1; i<= slen1; ++i)
{
//
for(j = 1; j<=slen2; ++j)
{
//
if(matchmap[i-1][j-1])
{
//
if(str1[i-1] == str2[j-1] || str2[j-1] == '?')
{
matchmap[i][j] = 1;
//
if( i == slen1 && j < slen2)
{
for ( k = j+1 ; k <= slen2 ; ++k )
{
if( '*' == str2[k-1])
{
matchmap[i][k] = 1;
}else{
break;
}
}
}
}else if(str2[j-1] == '*')
{
// ，
for(k = i-1; k<=slen1; ++k)
{
matchmap[k][j] = 1;
}
}
}
}
// ，
for(k = 1; k<=slen2; ++k)
{
if(matchmap[i][k])
{
break;
}
}
if(k>slen2)
{
return 0;
}
}
return matchmap[slen1][slen2];
}
// ， 。
char strMatch( const char *str1, const char *str2)
{
int slen1 = strlen(str1);
int slen2 = strlen(str2);
// strl
char matchmap[128][128];
memset(matchmap, 0, 128*128);
int i, j, k;
//
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(str1[i] == str2[j] || str2[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[k] ; ++k)
{
matchmap[i][k] = 1;
}
}
}else if(str2[j] == '*')
{
if(0 == bMatched)
{
lbound = j;
}
// ，
for(k = i; k< slen1; ++k)
{
matchmap[k][j] = 1;
}
k = j;
while( '*' == str2[++k])
{
matchmap[i][k] = 1;
}
if(str1[i] == str2[k] || str2[k] == '?')
{
matchmap[i][k] = 1;
upbound = k+1;
if(i == slen1 - 1)
{
// *
for(k = k+1 ; k < slen2 && '*' == str2[k] ; ++k)
{
matchmap[i][k] = 1;
}
}
}else{
upbound = k;
}
bMatched = 1;
}
}
//
if(!bMatched )
{
return 0;
}
}
return matchmap[slen1-1][slen2-1];
}