一个很难的字符串问题

作者: csdn-whinah 发表日期: 2012年02月20日分类: 自动机评论: 4 条阅读次数: 3,987 次

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

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

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

class MultiRegEx {
public:
    struct MatchResult {
        int nth; // regex NO.
        int beg; // begin of matched pos in text
        int end; // end of matched pos in text
    };

    // return the index NO. of the internal regex object, -1 indicate error
    int add(const char* regex);

    // compile the MultiRegEx
    bool compile();

    // length is the length of text
    vector<MatchResult> match(const char* text, int length) const;
};

class MultiRegEx {

public:

struct MatchResult {

int nth; // regex NO.

int beg; // begin of matched pos in text

int end; // end of matched pos in text

};

// return the index NO. of the internal regex object, -1 indicate error

int add(const char* regex);

// compile the MultiRegEx

bool compile();

// length is the length of text

vector<MatchResult> match(const char* text, int length) const;

};

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

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

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

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

2013-08-31：

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

4 个回复

stereohomology说道：

2013年10月30日上午12:16

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

登录以回复
whinah说道：

2013年11月3日下午8:43

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

登录以回复
lonelyrains说道：

2013年11月4日下午5:59

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

登录以回复
whinah说道：

2013年11月4日下午9:54

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

登录以回复

发表评论

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