-1

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

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

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

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

4

4 回答 4

5

在 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 *类型。如果您在同一个 haystack 中进行多次搜索，请尝试仅计算一次 haystack 长度。strlen不需要的时候不要打电话。

如果您的干草堆包含许多重复的第一个字符或针的字符，这将是非常不理想的。例如，在“aaaaaaaaaaaaaaaaaaaaaaaaaaaqaaaa..”中搜索“ab”（或者更糟的是，在“abababababababab...abc...”中搜索“abc”）会很慢。但是您没有为我们提供足够的细节来确定最佳实施方式。

问题的重点完全有可能是编写具有最佳最坏情况性能的算法。如果是这样，这可能不是“正确”的答案。可以想象一个所有 a 后面跟着一个 b 的大海捞针，以及一个由所有 a 后面跟着一个 b 组成的针。在那种情况下，这个算法可能需要很长时间。

于 2012-09-21T18:35:48.430 回答
4

这在我适中的第一代英特尔 iMac 上几乎立即完成（4 毫秒）。我将搜索字符串放在两个 100,000 个字符的块之间，以防 java 向后搜索。

StringBuilder builder = new StringBuilder();
for (int i = 0; i < 100000; i++) {
    builder.append((char) i);
}
builder.append("sub_string");
for (int i = 0; i < 100000; i++) {
    builder.append((char) i);
}
String maxString = builder.toString();
long t1 = System.currentTimeMillis();
System.out.println(maxString.contains("sub_string"));
long t2 = System.currentTimeMillis();
System.out.println(t2 - t1);

输出

true
4
于 2012-09-21T18:33:42.300 回答
1

假设java：

String.contains("stringtofind");

是一种查找字符串是否存在于另一个字符串javadoc中的方法。

于 2012-09-21T18:29:30.157 回答
1

在java中查找String内容的三种方式。

String.contains("charSequence");
String.contentEquals("charSequence");
String.contentEquals("StringBuffer");

并且您可以通过 Java 规范获得最大长度的字符串Integer.MAX_VALUE（总是）。2147483647 (2^31 - 1)

于 2012-09-21T18:31:51.650 回答