推荐: blog.csdn.net/aquester https://github.com/eyjian https://www.cnblogs.com/aquester http://blog.chinaunix.net/uid/20682147.html
全部博文(594)
分类: C/C++
2009-01-17 21:35:28
//方法一,从无通配符到有?再到有*,逐步推进分析 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]; }