一个理论问题。我有一个正则表达式。我想找到与此匹配的字符串。我怎样才能得到这些字符串的最小和最大长度？
最佳答案
将正则表达式转换为 NFA(如果需要，可以使用 epsilon 转换)。删除所有无法达到接受状态的状态(这可能是空操作)。最小长度是到接受状态的最短路径的长度(从起始状态使用 Dijkstra，其中带有符号的转换长度为 1，epsilon 转换长度为 0)。使用双端队列，这是线性时间。当且仅当存在循环时，最大长度为无穷大。否则，转换图是无环的；在无环图中使用最长路径算法。
关于regex - 如何找出与给定正则表达式匹配的字符串的最大和最小长度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30932860/