c++ - 比 O(n) glob 匹配器更好？

问题: 给定 globs 的列表，我需要从列表中找到(并返回)一个给定字符串匹配的 glob 或明确确定没有匹配的。排除设置时间，性能必须优于线性搜索所有的球体:

foreach glob in list:
  if glob.matches(string):
    return glob
return None

问题: 是否有任何可用的库(首选 C++)？

编辑:经过深思熟虑，我认为我可以争辩说这是可以做到的。鉴于 glob 或多或少是具有不同语法的正则表达式，使用 glob 语法的 lex 运行时版本将符合要求。

鉴于问题可以简单地简化为已知问题，我仍然只对已实现的解决方案感兴趣。

最佳答案

将您的 glob 转换为正则表达式(一系列简单的字符串操作可以实现这一点 - * 变成 .* 等)。将它们组合成一个正则表达式，使用 | 并将结果分配给每个 glob 的不同捕获组，以便您可以确定哪个 glob 匹配(如果有匹配)。依靠您最喜欢的正则表达式库将正则表达式编译成一个 DFA，希望它比组成部分的线性游走更易于处理，这是可能的 - 但是，在最一般的情况下，它不会更快。

关于c++ - 比 O(n) glob 匹配器更好？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5434209/