什么是最有效的通配符字符串匹配算法？我只问一个想法，没有必要提供实际的代码。
我认为这种算法可以用排序后缀数组构建，这可以产生O(log(n))的性能。
我对么？
编辑:
我的意思是像"A*B"，"*sip*"或"A?B"这样的模式，其中星号表示任意数量的符号，问号表示单个符号。
最佳答案
这里有一篇涵盖最快选择的论文
http://swtch.com/~rsc/regexp/regexp1.html
特别是，它允许您避免使用长模式时天真的算法在病理上变慢的幼稚算法。
它涵盖了通用正则表达式，但您可以将实现限制为所需的子集。