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

Question

我已经实现了一个用于模式搜索的 trie，并且运行良好。使用这个 trie，我可以找到 O(n) 复杂度的文本中出现的所有关键字。

问题是我想对我的模式(关键字)使用正则表达式，并想找到文本中出现的所有关键字。

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

例如，我将文本作为。examplegmail@gmail.com

关键字是:ample mail

在此示例中，此正则表达式将告诉我电子邮件 ID 的结束位置，但不会告诉我有关 ample 或 mail 关键字的任何信息。

编辑:假设我的正则表达式为 a*(b|cd?)+DFA 看起来像::

现在我在这些数据中有像 dfdfdacbcbbcb 这样的数据，它会告诉我到达 ac 之后的模式等等，但我该如何到达知道结束模式的长度吗？？？？

Answer 1

您的“trie”包含操作:“测试字符”“分支到第 n 个子树”。

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

将这些运算符插入您的(抽象)trie 规范中，编译为真正的 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”，以帮助解释模式匹配器结果的代码了解找到了哪些特殊关键字，以及如何解释位置索引。