📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5875| 回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : 字符串模糊匹配

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
*ac*bd*XXX???s 可以匹配 xcvabdf***XXX123s
*可以匹配一个或多个任意字符,?可以匹配一个任意字符。

bool match(const char* szPattern, const char* szString)

上一篇:Amazon : 设计一个并行运算的程序
下一篇:Google/Baidu : Find pervert pairs
🔗
darksteel 2011-4-29 13:51:54 | 只看该作者
全局:
是不是可以跟正则表达式似的,建立起自动机来进行匹配?
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-29 14:20:14 | 只看该作者
全局:
是不是可以跟正则表达式似的,建立起自动机来进行匹配?
darksteel 发表于 2011-4-29 13:51



    太复杂了,20行代码内解决
回复

使用道具 举报

🔗
DarthSidious 2011-4-29 15:00:14 | 只看该作者
全局:
简单的可以用动态规划做
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-29 15:14:09 | 只看该作者
全局:
简单的可以用动态规划做
DarthSidious 发表于 2011-4-29 15:00



    没必要用吧,感觉DP现在都泛滥了,什么问题都往DP上想
回复

使用道具 举报

🔗
Etrnls 2011-4-29 15:28:25 | 只看该作者
全局:
回复 3# wwwyhx


    20行搞定的时间复杂肯定是阶乘级别
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-29 15:32:28 | 只看该作者
全局:
回复  wwwyhx


    20行搞定的时间复杂肯定是阶乘级别
Etrnls 发表于 2011-4-29 15:28


额,那加个条件,不考虑时间复杂度,因为这种功能主要用在过滤个标题什么的。
指数复杂度也接受
回复

使用道具 举报

🔗
Etrnls 2011-4-29 15:40:10 | 只看该作者
全局:
本帖最后由 Etrnls 于 2011-4-29 15:56 编辑

  1. bool match(const char* szPattern, const char* szString)
  2. {
  3.     if (!*szPattern && !*szString)) return true;
  4.     if (!(*szPattern && *szString)) return false;
  5.     if ((*szPattern == *szString || *szPattern == '?' || *szPattern == '*') && match(szPattern + 1, szString + 1)) return true;
  6.     if (*szPattern == '*' && match(szPattern, szString + 1)) return true;
  7.     return false;
  8. }
复制代码
update: 空串忘检查了……
回复

使用道具 举报

🔗
darksteel 2011-4-29 23:16:01 | 只看该作者
全局:
回复 8# Etrnls
很不错的方法!
开始以为要实现像正则表达式那样的功能,给一个pattern然后能在文本中找出被匹配的子串,加上这学期学compiler就想到了自动机。这个方法时间复杂度最糟糕应该是指数的,可以通过记录信息避免重复计算降到M*N,我觉得上面说到的dp方法应该就是类似的想法。ls的写法已经很不错了,我稍微改写了下,看起来大概会更清晰点
  1. bool match(const char* szPattern, const char* szString)
  2. {
  3.     if (!(*szPattern || *szString)) return true;
  4.     if (!(*szPattern && *szString)) return false;
  5.     if (*szPattern == '*')
  6.             return match(szPattern, szString + 1) || match(szPattern + 1, szString + 1);
  7.     if (*szPattern == *szString || *szPattern == '?')
  8.             return match(szPattern + 1, szString + 1);
  9.     return false;
  10. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表