如何确定正则表达式中的子字符串？

Question

我已经实现了用于模式搜索的trie，并且工作正常。使用这个trie我可以找到所有在O（n）复杂文本中呈现的关键字。

问题是我想为我的模式（关键字）使用正则表达式，并希望找到文本中存在的所有关键字。

例如： 我写[a-z0-9 \。] {6，30} \ @ [a-z0-9 \。] {2,12} \。[a-z0-9] { 2,6}找到电子邮件ID，它会提取我正确的东西，但它不会找到第一或第二块下的子字符串。

例如我有文字为。 examplegmail@gmail.com

和关键字：ample mail

在这个例子中这个表达式会告诉我的电子邮件ID的结束位置，但它不会告诉任何关于ample或mail关键字。

编辑：假设我有正则表达式为一个*（？C | CD）+ 和DFA会是什么样子::

，现在我有一个像dfdfdacbcbbcb数据在这个数据它会告诉我在达到ac等在每个字符后的模式，但我怎么才能知道结束模式的长度？

Answer 1

你的“trie”包含操作：“test for char”“分支到第n个子树”。

添加另一个运算符来保存位置：“记住第N个字符索引”，它将当前字符位置写入字符串指针数组的第n个插槽中。

将这些运算符插入到您的（抽象）trie规范中，编译为真正的trie，然后运行它。由于特里匹配器“匹配”匹配中的各种关键点，它可以在字符串缓冲区中记录这些点。在最后的比赛中，你有一系列的指针（尽可能多的）到你的比赛的子部分。

对于示例：

[a-z0-9\.]{6, 30}\@[a-z0-9\.]{2,12}\.[a-z0-9]{2,6} 

想象我要挑文本左和中@的权利。

我添加位置运营商节约，这是我武断地表示为“＃N”：

#1[a-z0-9\.]{6, 30}#2\@[a-z0-9\.]{2,12}\.[a-z0-9]{2,6}#3 

这将（相当平凡）捕捉到起始位置时，“@”符号 的位置， （相当平凡）的最终位置，如位置1,2和3.当然，如果您觉得合适，您可以在中间更多。

[许多正则表达式系统在遇到分组操作符（...）时会隐式地执行此操作，从左到右对分组进行编号。这总是足够的，因为你总是可以在这样的分组操作符中包装一个有趣的子正则表达式。我喜欢明确的指示方案;阅读器和模式匹配器很清楚它必须插入这些位置捕获操作。我们已经实现了正则表达式匹配器，使用上面的#n符号。]。

如果您正在寻找各种各样的关键字和相关文本，您的trie可能有很多选择运算符。您可以在每个选择分支的适当位置添加这些位置捕捉操作符，以挑选出与该关键字相关的信息。您可能需要添加另一个运算符“识别关键字k”，以帮助解释模式匹配程序结果的代码了解找到了哪些特殊关键字，从而了解如何解释位置索引。