java - 在 Java 中搜索子字符串的最快方法是什么？

Question

我想了解在 Java 中进行子字符串搜索时可能出现的性能问题。我知道在 Java 中搜索子字符串的两种内置方法。

<强>1。 String.indexOf()

据我了解，此方法使用子字符串搜索的强力算法，因此其复杂度为 O(nm)，其中 n 和 m 是字符串和模式的长度。

<强>2。使用模式和匹配器

我对正则表达式算法的实现方式及其复杂性一无所知。

所以问题是:

1)从性能的角度来看，哪种方法更可取？

2) 正则表达式搜索的复杂度是多少？它取决于正则表达式本身吗？

Answer 1

老实说，如果您关心最坏情况下的性能，可以将 JNI 转换为调用标准库的 strstr 函数的 native 代码。实现良好的 strstr，就像最近版本的 glibc 中的那样，具有线性的最坏情况运行时间和恒定的最坏情况空间使用率。我相信 glibc 的 strstr 也可以在文本中进行类似于 Boyer-Moore 的长跳转。 C 标准库由知道如何编写和维护良好的通用库并实践其技能的人员维护。 Java 标准类库就不同了。

您必须将 Java UTF-16 字符串转换为适合 strstr 的内容，例如 UTF-8 字符串。您还必须优雅地处理 UTF-8 字符串中嵌入的零字节。除此之外，您将从编写良好且维护良好的库中获益。

Java 使用 Boyer-Moore 字符串搜索进行正则表达式搜索(对于这种特殊情况)，该字符串搜索被侵入到一个简单的正则表达式实现中。仅使用您的字符串编译 Pattern 将生成性能相对较好的 Matcher。但是请注意，这不会扩展到使用正则表达式库进行字符串搜索之外的任何内容；如果您向它提供一个非平凡的正则表达式，您仍然会遇到回溯的天真正则表达式实现。

为了证明为什么您不应该将 Java 正则表达式用于实际的正则表达式，我向您提供以下内容:

public class regex {
  public static void main(String[] args) throws Exception {
    String haystack = "ab";
    String needle = "abab?.*";
    for (int i = 0; i < 7; i++) haystack = haystack + haystack;
    for (int i = 0; i < 4; i++) needle = needle + needle;
    System.out.println(haystack.length() + " " + needle.length());
    long before = System.currentTimeMillis();
    System.out.println(Pattern.matches(needle, haystack));
    long after = System.currentTimeMillis(); // long after indeed...
    System.out.println(after - before);
  }
}

这是在 256 个字符的大海捞针中搜索 112 个字符的 needle 正则表达式(这是您在编译器类(class)中学到的诚实正则表达式)。在我的机器上完成大约需要 24 秒。