字符串匹配在Windows命令的使用中，有两个经常使用的通配符：*和?。*表示0个、1个或者多个字符，?表示0个或者1个字符。使用通配符可以利用dir命令搜索特定名字的文件。例如 引用： J:\WINDOWS\system32>dir msvc*dll 驱动器 J 中的卷是 WinXP 卷的序列号是 58A6-6950 J:\WINDOWS\system32 的目录2002-01-05  03:38            54,784 msvci70.dll2001-11-03  01:19            50,688 msvcirt.dll2001-11-03  01:19           565,760 msvcp50.dll2001-11-03  01:19           401,462 msvcp60.dll2002-01-05  03:40           487,424 msvcp70.dll2003-03-18  22:14           499,712 msvcp71.dll2002-01-05  03:37           344,064 msvcr70.dll2004-04-05  10:31           348,160 msvcr71.dll2001-11-03  01:19           322,560 msvcrt.dll2001-11-03  01:19           253,952 msvcrt20.dll2001-11-03  01:19            65,024 msvcrt40.dll              11 个文件      3,393,590 字节               0 个目录    822,599,680 可用字节 引用： J:\WINDOWS\system32>dir msvc???.dll 驱动器 J 中的卷是 WinXP 卷的序列号是 58A6-6950 J:\WINDOWS\system32 的目录2002-01-05  03:38            54,784 msvci70.dll2001-11-03  01:19            50,688 msvcirt.dll2001-11-03  01:19           565,760 msvcp50.dll2001-11-03  01:19           401,462 msvcp60.dll2002-01-05  03:40           487,424 msvcp70.dll2003-03-18  22:14           499,712 msvcp71.dll2002-01-05  03:37           344,064 msvcr70.dll2004-04-05  10:31           348,160 msvcr71.dll2001-11-03  01:19           322,560 msvcrt.dll               9 个文件      3,074,614 字节               0 个目录    822,599,680 可用字节注意：msvcrt.dll也能被msvc???.dll匹配，那是因为有一个?匹配到0个字符。本次比赛的题目就是实现类似的功能，测试程序提供形如msvc???.dll或dir msvc*dll格式的“模式串”，以及形如msvcrt.dll的“目标串”，由你来判断二者能否匹配。接口定义：bool IsMatch(const char * pattern, const char * target); // for C++ true=匹配、false=不匹配int IsMatch(/*const*/ char * pattern, /*const*/ char * target); // for C 1=匹配、0=不匹配pattern=模式串target=目标串注意：使用C的朋友即便是开发环境不支持const，也不要更改pattern和target的内容。以下一些功能可以自行选择：1、测试时?和*是否至少匹配1个字符，也就是说???是否能够与rt匹配？同样，“*”是否匹配1个或多个字符。2、测试时是否需要保证?与*不会连用，*与*也不会连用，即不会出现例如msvc??*.dll、msvc?**.dll等情况？但是例如ms*c???.dll等情况是必须考虑的。如果你的程序能够处理连用的情况，那么该程序可以在其他结果相同的条件下胜出。以下是要注意的几点：1、?不能与标点符号匹配，只能与字母和数字还有下划线（_）匹配，但是*可以。这一点和实际使用是符合的，例如 引用： J:\WINDOWS\system32>dir msvcrt.dll 驱动器 J 中的卷是 WinXP 卷的序列号是 58A6-6950 J:\WINDOWS\system32 的目录2001-11-03  01:19           322,560 msvcrt.dll               1 个文件        322,560 字节               0 个目录    822,566,912 可用字节J:\WINDOWS\system32>dir msvcrt?dll 驱动器 J 中的卷是 WinXP 卷的序列号是 58A6-6950 J:\WINDOWS\system32 的目录找不到文件J:\WINDOWS\system32>dir msvcrt*dll 驱动器 J 中的卷是 WinXP 卷的序列号是 58A6-6950 J:\WINDOWS\system32 的目录2001-11-03  01:19           322,560 msvcrt.dll2001-11-03  01:19           253,952 msvcrt20.dll2001-11-03  01:19            65,024 msvcrt40.dll               3 个文件        641,536 字节               0 个目录    822,505,472 可用字节 2、区分大小写，IsMatch("mSvCrT.dll","msvcrt.dll")返回false。测试规则：1、测试时能够处理简单的单个?或*情况（每个?或*至少匹配一个字符），例如msvcrt.dll、msvcr?.dll，则为Pass I。2、在Pass I通过的条件下能够处理?连用（例如msvc??.dll、msvc???.dll）则为Pass II。3、在Pass II通过的条件下如果能够处理多组通配符，例如ms*c???.dll，则为Pass III。4、在Pass III的基础上能够处理连用的情形，例如msvc*??.dll，则为Pass IV。5、在Pass IV的基础上能够让*和?匹配空字符，即允许*和?匹配0个字符，则为Pass V。获得最高Pass等级者优胜。优胜者中代码优秀者为冠军。 依次对模式串中的字符分3种情况讨论：1、问号“?”首先跳过这个?号，第归测试余下的模式串和目标串能否匹配（目标串和模式串分别有各自的游标指针）。这就相当于暂且让“?”进行空匹配，看能否符合。如果余下的匹配失败，那么看“?”能否与目标串游标当前字符匹配，如果不能（?不能与.匹配），返回false。如果能，再第归测试余下的模式串和目标串能否匹配。例如：?asdf asdf尝试空匹配，成功（asdf == asdf）又例如?asdf fasdf尝试空匹配，失败（asdf != fasdf）再看?能否与f匹配？（可以），asdf能否与asdf匹配？（可以），则成功。又例如?asdf fasd尝试空匹配，失败（asdf != fasd）再看?能否与f匹配？（可以），asdf能否与asd匹配？（不行），则失败。又例如?asdf .asdf尝试空匹配，失败（asdf != .asdf）再看?能否与.匹配？（不行），则失败。2、星号“*”首先跳过这个*号，原理和上面一样，首先尝试空匹配。如果无法匹配为空，那么每次移动目标目标串游标，看余下的能否匹配，当第归到下一层时，由于重视尝试空匹配，在这里就相当于尝试*的终结。例如下面的过程：*asdf asdfasdf进入下一层第归时变为*asdf sdfasdf空匹配肯定失败（asdf!=sdfasdf）再进入下一层第归变为*asdf dfasdf空匹配还是失败（asdf!=dfasdf）再进入下一成第归*asdf fasdf空匹配还是失败（asdf!=fasdf）再进入下一成第归*asdf asdf空匹配成功，返回true。（asdf==asdf）最终结果当然也是成功的。3、其他符号其他符号直接与目标串对应字符比较。如果不区分大小写的话，那么将字母全部转换为大写或小写进行比较。 测试程序下载测试包内的文件说明如下：main.cpp 主程序文件，包含测试直接使用的宏。Tester.h 功能测试文件，包含了全部31个测试数据和及其对应的对象封装。ns.h 命名空间相关的宏，自动给每个参赛者的名字空间里添加new、delete、malloc、free的重载以及时间测量函数。timer.h 用来测量时间的对象，封装了求均值、方差、标准差等功能。memctrl.h 内存跟踪对象，重载new、delete、malloc、free等操作。SonicLing.h 我的算法。测试数据的标准匹配结果就是用我的算法生成的，然后大家的结果和我生成的标准结果比较。其余匹配*_*.h格式的文件就是大家的代码了。（完）

评论