c++ - 通配符字符串搜索算法

Question

在我的程序中，我需要在一个相当大的字符串(~1 mb)中搜索相对较小的子字符串(< 1 kb)。 问题是字符串包含“a？c”意义上的简单通配符，这意味着我想搜索像“abc”或“apc”这样的字符串，...(我只对第一次出现感兴趣)。

到目前为止，我使用的是简单的方法(此处为伪代码)

algorithm "search", input: haystack(string), needle(string)

for(i = 0, i < length(haystack), ++i)
 if(!CompareMemory(haystack+i,needle,length(needle))
  return i;

return -1; (Not found)

如果第一个和第二个参数相同(也涉及通配符)，“CompareMemory”返回 0，仅与第三个参数给出的字节数有关。

我现在的问题是是否有一个快速算法(你不必给出它，但如果你给出，我更喜欢 c++、c 或伪代码)。我开始here 但我认为大多数快速算法不允许使用通配符(通过它们利用字符串性质的方式)。

我希望问题的格式没问题，因为我是新来的，提前谢谢你!

Answer 1

一种快速的方法，与使用正则表达式相同(无论如何我都会推荐)，是找到固定在“a”而不是“?”中的东西，然后搜索，然后看看您是否有完整的匹配。

j = firstNonWildcardPos(needle)
for(i = j, i < length(haystack)-length(needle)+j, ++i)
  if(haystack[i] == needle[j])
    if(!CompareMemory(haystack+i-j,needle,length(needle))
      return i;

return -1; (Not found)

正则表达式会生成与此类似的代码(我相信)。