通配符字符串匹配

Question

什么是最有效的通配符字符串匹配算法？我只询问一个想法,没有必要提供实际的代码.

我认为这样的算法可以使用排序的后缀数组构建,这可以产生O(log(n))的性能.

我对么？

编辑:

我的意思是模式"A*B","*sip*"或者"A?B"星形意味着任意数量的符号,而问号意味着单个符号.

Answer 1

嗯，我认为正常的模式匹配规则适用于此。通常，由于您有数据流和短模式，因此您不需要实现比线性更有效的东西。然而，模式越长，优化的空间就越大。

您想要什么样的通配符？单字符通配符（例如.在正则表达式中）或多字符通配符（例如.*）？有限制吗？预期的模式长度是多少？您是否可以随机或串行访问要检查的数据？