检查字符串是否可用更长的100,000字符串

Question

可能重复:
什么是最快的子字符串搜索算法？

如何检查字符串是否存在于C++或Java中长度为100,000个字符的较大字符串中？

我知道一种方法,str.find("sub_string");但它无法处理如此大的字符串.最长执行时间为1秒.

我需要寻找的子字符串也可以是50,000!

Answer 1

在C或C++中,您可以使用malloc获取100,000字节的块.填写您的数据.要在大海捞针中找到针,可以使用以下代码:

void *mem_mem(void *haystack, int haystack_len, void *needle, int needle_len)
{
  const char *begin;
  const char *const last_possible
    = (const char *) haystack + haystack_len - needle_len;

  if (needle_len == 0)
    return (void *) &((const char *) haystack)[needle_len - 1];

  for (begin = (const char *) haystack; begin <= last_possible; ++begin)
    if (begin[0] == ((const char *) needle)[0] &&
    !memcmp ((const void *) &begin[1],
         (const void *) ((const char *) needle + 1),
         needle_len - 1))
      return (void *) begin;

  return NULL;
}

在任何合理的现代平台上,这将在很短的一秒钟内找到100,000字节的任何子字符串.您可以修改它以轻松使用char *类型.如果您在同一个大海捞针中进行多次搜索,请尝试仅计算一次干草堆长度.不需要strlen时不要打电话.

如果您的草垛包含许多重复的第一个字符或针的字符,这将是非常不理想的.例如,在"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaqa ..."中搜索"ab"(或者更糟糕的是,在"abababababababab ... abc ......"中搜索"abc")将会很慢.但是你没有给我们足够的细节来确定最佳实施方案.

完全可能的问题是编写具有最佳可能最差情况性能的算法.如果是这样,这可能不是"正确"的答案.人们可以想象一个大海捞针,最后是一个b,一个针由所有a组成,后面跟着一个b.在这种情况下,此算法可能需要很长时间.