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

Question

我需要实现一种使用 Java 在字符串列表 (haystack) 中搜索子字符串 (needles) 的方法。

更具体地说，我的应用程序有一个用户配置文件列表。如果我输入一些字母，例如“Ja”，然后进行搜索，那么应该会显示名称中包含“ja”的所有用户。例如，结果可能是“Jack”、“Jackson”、“Jason”、“Dijafu”。

据我所知，在 Java 中，有 3 种内置方法可以在字符串中查看搜索子字符串。

1. string.contains()

2. string.indexOf()

3. 正则表达式。它类似于 string.matches("ja"))

我的问题是:上述每个方法的运行时间是多少？哪一个是检查字符串列表是否包含给定子字符串的最快、最有效或最流行的方法。

我知道有一些算法可以做同样的事情，例如 Boyer–Moore 字符串搜索算法、Knuth–Morris–Pratt 算法等。我不想使用它们，因为我只有一小部分字符串，而且我认为现在使用它们对我来说有点矫枉过正。此外，我还必须为这种非内置算法输入大量额外的代码。如果您认为我的想法不正确，请随时纠正我。

Answer 1

接受的答案不正确且不完整。

• indexOf() 使用不匹配的回溯进行简单的字符串搜索。这在小图案/文本上相当快但在大文本上表现非常差
• contains("ja") 应该与 indexOf 相当(因为它委托(delegate)给它)
• matches("ja") 不会提供正确的结果，因为它会搜索完全匹配(只有字符串 "ja" 会完全匹配)<
• 模式 p = Pattern.compile("ja");匹配器 m = p.matcher("jack"); m.find(); 将是使用正则表达式查找文本的正确方法。在实践中(使用大文本)这将是仅使用 java api 的最有效方式。这是因为常量模式(如 "ja")不会由正则表达式引擎(速度慢)处理，而是由 Boyer-Moore-Algorithm(速度快)处理