一个很难的字符串问题

有 n 个 RegEx (正则表达式),标号从 0 到 n-1,n 可能很大 (比如说100万)。

问题:给定一个字符串,返回能 match 这个字符串的所有正则表达式标号。

用 C++ 来描述这个需求:

这个问题看上去简单,但其实现非常复杂!一个简单生硬的实现是,随便拿一个正则表达式引擎(如boost.regex, pcre, re2, …),match 时逐个匹配,匹配成功的,加入返回值集合。但这个时间复杂度太高!

原则上,unix 下的 lex 可以匹配多个 RegEx,并返回那个被匹配的 RegEx 标号,但好像无法识别多个成功的 RegEx 匹配。

这个问题的一个简化版:这 n 个 RegEx 只是简单的 PlainString,就是 Multi String Match 问题,甚至是这个简化版,其实现复杂多都相当高(trie, double array, …)。

我找了很多资料,好像都没有特别合适的办法。

 

2013-08-31:

google re2 中有同时匹配多个正则表达式的功能,可惜还是有些缺陷,正在做自己的引擎,克服那些缺陷

作者:
该日志由 csdn-whinah 于2012年02月20日发表在自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 一个很难的字符串问题
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

4 个回复

  1. stereohomology说道:

    请教,很多Linux下的库,如何转成VC的project file的?有没有诀窍或者专用的工具?

  2. whinah说道:

    好像不能,开源界有个 CMake 工具,跨平台,可以从 CMake 脚本生成 vcproj 和 Makefile

  3. lonelyrains说道:

    可以从这N个正则表达式的联系入手分析吗?构建正则表达式群或者树之类的. 起码有的可能排斥或者等价吧.

  4. whinah说道:

    [reply]lonelyrains[/reply]
    参考这篇:http://blog.csdn.net/whinah/article/details/14109083

发表评论

您必须 登录 后才能发表评论。