一个字符串匹配问题

一个很难的字符串问题

（来自google group的一条帖子）

---------- Forwarded message ----------

我提一个特殊情况的解法. 直观上觉得算法效率应该可行, 但是实际操作起来还有待考虑.
或许考虑有些疏漏, 望指出.
可行性需要根据具体输入值情况. 或需要继续研究, 有兴趣的可以继续思考.
--
假设, RegEx 表达式包含的字符数目m不多，或其数目n不太大的情况.
1. 针对RegEx包含的m个字符做赋值映射, 再依次将每个RegEx值预处理, 如abc -> c+b*m+a*m*m
转化成一个整型数值pre_values[1 ... n]; 时间复杂度 O(m + n).

2. 排序集合pre_values; 时间复杂度O (n*log(n))
.
3. 从给定字符串in_str获取子串并根据上面规则, 预处理子串转化为整型数值value, 到pre_values匹配.
构建子串:
a 从in_str第一字符作为子串的首字符, 直至最后一个字符作为子串的首字符.
b 确定好子串首字符, 即依次在其后添加字符,作为子串.
c 若子串转化的数值大于pre_value最大值value_max, 则停止.开始下一个字符作为子串的字符.

时间复杂度:
子串的个数, 估算为n *  x (x为不确定数值, x <= n, 且x数值呈现渐小状态).最糟糕情况,  n + (n-1) ...+1 = n(n-1)/2  -> O(n^2).
遍历pre_values次数,  n * x * log(n) - > O(n^2 * log(n))


ps. 该步骤应该是算法的难点.

4. 重复步骤3直至结束以in_str最后一字符作为子串的匹配操作. 记录过程中的匹配结果.
--
... ...

欢迎讨论，拍砖！

> 问题描述：

> 有 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;
>     };

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

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

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

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