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

Question

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

更具体地说,我的应用程序有一个用户配置文件列表.如果我输入一些字母,例如"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相当(因为它委托给它)
• matches("ja")将无法提供正确的结果,因为它会搜索完全匹配(只有字符串"ja"才会完全匹配)
• Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find();将是使用正则表达式查找文本的正确方法.在实践中(使用大文本),它将是仅使用java api 的最有效方式.这是因为"ja"正则规则引擎(慢速)不会处理常量模式(如),而是Boyer-Moore算法(速度快)

Answer 2

就你所问的三个而言,正则表达式会慢得多,因为当你有一个更简单的目标时,它需要组合一个完整的状态机.对于containsvs indexOf...

2114 public boolean contains(CharSequence s) {
2115     return indexOf(s.toString()) > -1;
2116 }

(也就是说,contains只是调用indexOf,但是你可能会String在每次调用时产生额外的创建.这只是一个实现contains,但由于契约contains是一个简化indexOf,这可能是每个实现的工作原理.)

Answer 3

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