中级农民
- 积分
- 128
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-2-8
- 最后登录
- 1970-1-1
|
回复 8# Etrnls
很不错的方法!
开始以为要实现像正则表达式那样的功能,给一个pattern然后能在文本中找出被匹配的子串,加上这学期学compiler就想到了自动机。这个方法时间复杂度最糟糕应该是指数的,可以通过记录信息避免重复计算降到M*N,我觉得上面说到的dp方法应该就是类似的想法。ls的写法已经很不错了,我稍微改写了下,看起来大概会更清晰点
- bool match(const char* szPattern, const char* szString)
- {
- if (!(*szPattern || *szString)) return true;
- if (!(*szPattern && *szString)) return false;
- if (*szPattern == '*')
- return match(szPattern, szString + 1) || match(szPattern + 1, szString + 1);
- if (*szPattern == *szString || *szPattern == '?')
- return match(szPattern + 1, szString + 1);
- return false;
- }
复制代码 |
|