我正在开发一个小型搜索引擎来显示具有完整路径的匹配文件名。重要的是我需要提供通配符（GLOB）搜索，例如*.doc或*list*.xlx或*timesheet*或???.doc或类似的东西。
我找到了一些相关的解决方案
在小于 O(n) 的时间内搜索匹配模式“abc:*:xyz”的字符串
但我正在寻找有效的算法，它可以在不到一秒的时间内从数百万个文件名中找到匹配项，因此需要比 O(n) 更好。
我正在考虑在第一阶段使用子字符串数组（后缀数组+前缀数组）搜索和通过第一阶段第二阶段的结果进行正常正则表达式搜索的两阶段算法。
任何帮助将不胜感激...
查看自我索引：这个 Stack Overflow 问题，以及关于它的这篇 DrDobbs 文章。
据我所知，对于广义全局搜索，没有办法比 O(n) 做得更好。
但是对于前缀和后缀搜索的特殊情况，您可以让自己排序索引以进行二进制搜索，导致前缀和后缀搜索的 O(log n)。前缀索引将根据第一个字符排序，然后是第二个，依此类推。后缀索引将根据最后一个字符排序，然后是倒数第二个，依此类推（反向字符串）。
我会按照您在帖子中的建议进行搜索，分两个阶段进行搜索，搜索前缀或后缀索引，然后使用从 glob 生成的正则表达式通过第一阶段提供的简化列表进行强力搜索。
由于字符串长度比较比正则表达式更快，我还将预先过滤最小匹配字符串长度，或 ???.doc 示例的固定长度匹配字符串。
从您原始帖子的声音来看，索引也需要引用每个条目的完整路径，以便您可以在找到最终结果后显示它。