什么是Java中最快的子字符串搜索方法
我需要实现一种使用Java搜索字符串（haystack）列表中的子字符串（针）的方法。
更具体地说，我的应用程序有一个用户配置文件列表。 如果我输入一些字母，例如“Ja”，然后搜索，则所有名称中包含“ja”的用户都应该显示。 例如，结果可能是“Jack”，“Jackson”，“Jason”，“Dijafu”。
在Java中，据我所知，有3种内置方法可以在字符串中查看搜索子字符串。
-
string.contains（）
-
string.indexOf（）
-
正则表达式。 它就像string.matches（“ja”））
我的问题是：上面每种方法的运行时间是多少？ 哪一个是检查字符串列表是否包含给定子字符串的最快或最有效或最流行的方法。
我知道存在一些做同样事情的算法，例如Boyer-Moore字符串搜索算法，Knuth-Morris-Pratt算法等等。 我不想使用它们，因为我只有一小串字符串，我认为使用它们对我来说有点矫枉过正。 此外，我必须为这种非内置算法输入许多额外的编码。 如果您认为我的想法不正确，请随时纠正我。
String[] names = new String[]{"jack", "jackson", "jason", "dijafu"}; long start = 0; long stop = 0; //Contains start = System.nanoTime(); for (int i = 0; i < names.length; i++){ names[i].contains("ja"); } stop = System.nanoTime(); System.out.println("Contains: " + (stop-start)); //IndexOf start = System.nanoTime(); for (int i = 0; i < names.length; i++){ names[i].indexOf("ja"); } stop = System.nanoTime(); System.out.println("IndexOf: " + (stop-start)); //Matches start = System.nanoTime(); for (int i = 0; i < names.length; i++){ names[i].matches("ja"); } stop = System.nanoTime(); System.out.println("Matches: " + (stop-start)); 输出：
Contains: 16677 IndexOf: 4491 Matches: 864018
接受的答案不正确且不完整。
-
indexOf()使用不匹配的回溯来进行简单的字符串搜索。 这在小图案/文本上非常快，但在大文本上表现非常差 -
contains("ja")应与indexOf相当（因为它委托给它） -
matches("ja")将无法提供正确的结果，因为它会搜索完全匹配（只有字符串"ja"才会完全匹配） -
Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find();是找到正则表达式文本的正确方法。 在实践中（使用大文本），它将是仅使用java api 的最有效方式。 这是因为正则规则引擎（慢速）不会处理常量模式（如"ja"），而是Boyer-Moore算法（速度快）
就你提到的三个问题而言，正则表达式会慢得多，因为当你有一个更简单的目标时，它需要组合一个完整的状态机。 对于contains vs indexOf …
2114 public boolean contains(CharSequence s) { 2115 return indexOf(s.toString()) > -1; 2116 }
（即，只contains调用indexOf ，但是你可能会在每次调用时产生额外的String 。这只是contains一个实现，但由于contains的契约是indexOf的简化，这可能是每个实现都有效的方法。）
从您问题中的示例，我假设您要进行不区分大小写的比较。 这些都大大减缓了这个过程。 因此，如果你可以忍受一些不准确 – 这可能取决于你需要进行比较的区域设置，并且你的长文本被反复搜索，将长文本一次转换为大写可能是有意义的，搜索字符串，然后搜索不区分大小写。
如果您正在搜索大量字符串，我已经阅读过Aho-Corasick算法的速度非常快，但它本身是用Java实现的。 这与GREP在基于Unix的系统中使用的算法相同，如果这有帮助并且非常有效。 这是一个Java实现，由Berkley提供。
另见： https ： //stackoverflow.com/a/1765616/59087
这取决于特定的JRE（甚至是JDK）make / version。 它还取决于/可能取决于字符串长度，被包含的概率，在什么位置等因素。获得精确性能数据的唯一方法需要设置您的确切上下文。
但是，通常aString.contains()和aString.indexOf()应该完全相同。 即使正则表达式得到了极好的优化，它也不会超过前两个表达式。
不，Java也不使用非常专业的算法。