确定正则表达式是否是另一个的子集
发布时间：2020-12-14 06:41:13 所属栏目：百科 来源：网络整理
导读：我有一个大的正则表达式的集合，当匹配调用一个特定的http处理程序。一些旧的正则表达式是不可达的(例如a.c *?abc *)，我想修剪它们。 是否有一个库，给了两个正则表达式会告诉我，如果第二个是第一个的子集？ 我不知道这是可以决定的(它闻起来像停止问题，
|
我有一个大的正则表达式的集合，当匹配调用一个特定的http处理程序。一些旧的正则表达式是不可达的(例如a.c *?abc *)，我想修剪它们。
是否有一个库，给了两个正则表达式会告诉我，如果第二个是第一个的子集？ 我不知道这是可以决定的(它闻起来像停止问题，一个不同的名字)。但事实证明it’s decidable。
Trying to find the complexity of this problem lead me to this paper.
问题的正式定义可以在这里找到：这通常被称为包含问题
这篇文章有一些伟大的信息(总结：所有，但最简单的表达式是相当复杂)，然而搜索关于包含问题的信息直接一个回到StackOverflow的答案已经有一个链接到a paper describing a passable polynomial time algorithm应该覆盖很多常见的情况。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |