如何设计用于搜索模式的正则表达式，而不是验证模式？

Question

正如我们所了解的，给定正则表达式模式(例如，A B A B A C)，我们可以将其转换为DFA。在这个例子中，它就像一个链(您可以测试它这里)。

这个“链式”DFA可以判断给定的字符串是否与模式匹配(即接受/拒绝它)；但不能判断字符串中是否有任何事件，并标识所有字符串。

示例：假设这是要搜索的字符串：A B C A B A B A B A C A B C

虽然有一个从第6个字符开始的事件，但“链状”DFA无法分辨这一点。它所能做的就是拒绝这个字符串。

问题：是否有可能设计支持这种功能的正则表达式？

(注:我理解这个问题有点令人困惑，我想澄清一下，它使你感到困惑。)

Answer 1

包含子字符串ABABAC的字符串的语言由正则表达式匹配：

.*ABABAC.*

其中，符号.表示与任何单个输入符号匹配的子表达式(例如，如果输入语言只有符号A、B和C，则为(A|B|C) )。要判断一个字符串是否有子字符串ABABAC，可以从这个正则表达式构建NFA或DFA，并检查它是否接受您的字符串。

使用(单个)标准N/DFA无法确定子字符串在输入字符串中的位置，因为定义了一个N/DFA只返回一位信息(接受/拒绝)。但是，可以实现一个“增广N/DFA”，该“增广N/DFA”除了匹配输入之外，还可以跟踪每个状态转换在字符串中最后发生的位置；该信息足以有效地重建子字符串的位置。