带通配符的字符串比较

2024年5月4日 互联网

带通配符字符串比较

      字符串中含有“*”和“？”如何实现匹配。算法不用解释，看代码就明白了。

#include <iostream>
#include <string>
#include <sstream>
using namespace std;//顺边贴一个任意类型转string的代码
template<class T>
string ToString(T flag)
{stringstream ret;ret<<flag;return ret.str();
}string Bool2String(bool arg){return arg?"Yes":"No";
}bool CommonMatch(char *str,char *subStr)
{if(*subStr == '\0')return true;if(*str == '\0')return false;if(*subStr == *str)return false;return CommonMatch(str+1,subStr+1);
}bool IsMatch(char* str, char* pattern)
{if(*pattern == '\0')return true;if(*pattern == '*'){while(*str!='\0'){if(IsMatch(str++,pattern+1))return true;}}if(*str == '\0')return false;if(*str == *pattern || *pattern == '?')return IsMatch(str+1,pattern+1);if(*str != *pattern)return false;
}int main()
{char str[] = "ttest";char subStr[] = "t*t";cout<<Bool2String(CommonMatch(str,subStr))<<endl;cout<<Bool2String(IsMatch(str,subStr))<<endl;system("pause");return 0;
}

通配符字符串匹配（http://blog.csdn.net/mark2you/article/details/6268721）

对于t（t是带匹配的字符串），可以看成被一些*串（连续的*组成的子串）划分成了一组跟s一样纯由字母组成的子串。
这样问题就转化成了在s中寻找一个子串序列。

  1. 开始时还像普通的串匹配一样，移动s和t，直到t遇到第一个*
  2. 然后t后面的部分假设被*串划分成如下一组字符字串：t1, t2, t3
  3. 那么问题变成了从s的当前位置开始找t1，如果没找到，则不匹配；如果找到（这时候有可能s中存在很多t1，我们只需考虑第一个。因为如果第一个能导致整个串匹配成功，则已经达到我们的目的，其他的不用考虑，因为我们并不需要输出所有的匹配。而如果第一个都不能使整个串匹配成功，后面情况由于可供匹配的子串更短，更不可能成功。），则继续从s匹配了t1的部分后面继续找t2；如此操作直至所有的子串都找到时，则整个匹配成功，否则任何一处没匹配则整个匹配失败。

最新文章