返回信息流字符串1：只含有英文字母，
字符串2：含有英文字母和*，其中符号*表示匹配任意字符0或者多次，即正则表达式里面的含义。
现在给定这样的两个串，要求判断是否匹配？
bool isMatch ( const char *str1, const char *str2)
例如：str1 = "hello", str2 = "he*o"，则二者匹配，返回true,
str1 = "hello", str2 = "he*l"，则不匹配，返回false。
这是一条镜像帖。来源：北邮人论坛 / cpp / #32011同步于 2009/11/24
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
一道字符串匹配题目，有兴趣的进来。
camelBUPT
2009/11/24镜像同步11 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
既然是正则表达式，就可以用自动机解决吧
【 在 camelBUPT (迷茫的人) 的大作中提到: 】
: 字符串1：只含有英文字母，
: 字符串2：含有英文字母和*，其中符号*表示匹配任意字符0或者多次，即正则表达式里面的含义。
: 现在给定这样的两个串，要求判断是否匹配？
: ...................
当*t不是*的时候, 就像普通的串匹配一样, 移动s和t
当*t是*的时候, 假设*t后面第一个不是*的字符是x, 若x是null, 直接匹配成功, 否则在s中找到当前位置后所有字符x的位置, 这时候问题转化成了t中x后的串和s中当前位置以后所有以x为开始的串的匹配问题, 递归调用即可, 其中任意一个匹配成功, 则原串匹配成功, 若都没有匹配成功则匹配失败.
当*s和*t其中一个是null时 跳出循环, 若此时 *t == '*', 则++t 直到 t != '*', 这时若 *t == 0 则代表匹配成功, 否则匹配失败
稍微调试了一下，不知道还有没有错误
#include <cstring>
#include <iostream>
using namespace std;
bool is_match(const char * s, const char * t)
{
while (*s && *t)
{
if (*t != '*' && *s == *t)
++s, ++t;
else if (*t != '*' && *s != *t)
return false;
else if (*t == '*')
{
do ++t; while (*t == '*');
if (*t == 0) return true;
for ( ; *s; ++s)
if (*s == *t && is_match(s+1, t+1))
return true;
return false;
}
}
while (*t == '*') ++t;
if (*s == *t) return true;
else return false
}
int main(int argc, char * argv[])
{
if (is_match(argv[1], argv[2]))
cout << "match" << endl;
else cout << "not match" << endl;
return 0;
}
非常棒，谢谢！！！
【 在 jokerlee 的大作中提到: 】
: 当*t不是*的时候, 就像普通的串匹配一样, 移动s和t
: 当*t是*的时候, 假设*t后面第一个不是*的字符是x, 若x是null, 直接匹配成功, 否则在s中找到当前位置后所有字符x的位置, 这时候问题转化成了t中x后的串和s中当前位置以后所有以x为开始的串的匹配问题, 递归调用即可, 其中任意一个匹配成功, 则原串匹配成功, 若都没有匹配成功则匹配失败.
: 当*s和*t其中一个是null时 跳出循环, 若此时 *t == '*', 则++t 直到 t != '*', 这时若 *t == 0 则代表匹配成功, 否则匹配失败
: ...................
加上记忆化递归效率就会高一些
【 在 jokerlee 的大作中提到: 】
: 当*t不是*的时候, 就像普通的串匹配一样, 移动s和t
: 当*t是*的时候, 假设*t后面第一个不是*的字符是x, 若x是null, 直接匹配成功, 否则在s中找到当前位置后所有字符x的位置, 这时候问题转化成了t中x后的串和s中当前位置以后所有以x为开始的串的匹配问题, 递归调用即可, 其中任意一个匹配成功, 则原串匹配成功, 若都没有匹配成功则匹配失败.
: 当*s和*t其中一个是null时 跳出循环, 若此时 *t == '*', 则++t 直到 t != '*', 这时若 *t == 0 则代表匹配成功, 否则匹配失败
: ...................