logo标签列表

算法：两个正则表达式的交集

c#algorithm
3

我希望能够在运行时确定两个正则表达式是否相交（即，如果它们相交，则存在一个或多个字符串匹配两个正则表达式）。

算法需要相当快，因为我需要遍历数据库并检查现有值。

找到了一些相关理论，但没有实现吗？

Oracle还是SQL数据库？Oracle支持正则表达式，而SQL不支持。 - jcollum
3个回答
3
显而易见的解决方案是将正则表达式转换为DFA，计算DFAs的交集（平凡），并查看生成的DFA是否能接受任何内容（同样平凡）。唯一困难的部分是将正则表达式转换为DFA，这需要一些工作。
3
这里有一个使用正则表达式的偏导数实现的 Haskell示例。该帖子的评论指出了Chris Dodd答案中的一个问题。
0

先检查第一个，然后再用通过第一个的输入检查第二个怎么样？

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接