我有一个可能的子串列表,例如['cat','fish','dog'].实际上,该列表包含数百个条目.
我正在处理一个字符串,我正在寻找的是找到任何这些子字符串的首次出现的索引.
为了澄清,对于'012cat',结果是3,对于'0123dog789cat',结果是4.
我还需要知道找到了哪个子字符串(例如,它在子字符串列表中的索引或文本本身),或者至少是匹配的子字符串的长度.
有明显的蛮力方法来实现这一点,我想知道是否有任何优雅的Python/Regex解决方案.
谢谢,Rax
可以编写一个在某些情况下需要指数运行时间的正则表达式.这样的例子是(aa|aa)*.如果输入奇数个as,则需要指数运行时间.
这很容易测试.如果输入仅包含as并且长度为51,则正则表达式需要几秒钟才能计算(在我的机器上).相反,如果输入长度为52,则其计算时间不明显(我使用JavaRE的内置Regex-parser对其进行了测试).
我写了一个正则表达式解析器来找到这种行为的原因,但我没有找到它.我的解析器可以基于正则表达式构建AST或NFA.之后,它可以将NFA翻译为DFA.为此,它使用了powerset构造算法.
当我解析上面提到的Rgex时,解析器会创建一个具有7种状态的NFA - 转换后,DFA中只剩下3个状态.DFA代表更明智的正则表达式(aa)*,可以非常快速地解析.
因此,我不明白为什么有解析器可以这么慢.这是什么原因？他们不会将NFA翻译成DFA吗？如果是的话,为什么不呢？他们计算得如此之慢的技术原因是什么？