在Java中搜索子字符串的最快方法是什么？
我想了解在Java中进行子字符串搜索时可能出现的性能问题。 我知道在Java中搜索子字符串的两种内置方法。
1. String.indexOf（）
据我所知，这种方法使用子串搜索的powershell算法，因此其复杂度为O（nm），其中n和m是字符串和模式的长度。
2.使用模式和匹配器
我对正则表达式算法的实现方式及其复杂性一无所知。
所以问题是：
1）从性能的角度来看，哪种方法更受欢迎？
2）正则表达式搜索的复杂性是什么？ 它取决于正则表达式本身吗？
老实说，如果你关心最坏情况的性能，那么将JNI转换为调用标准库的strstr函数的本机代码。 良好实现的strstr ，就像最近版本的glibc中那样，具有线性最坏情况运行时间和恒定最坏情况空间使用。 我相信glibc的strstr也可以在文本中做类似Boyer-Moore的strstr 。 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个字符的针正则表达式（这是你在编译器类中学到的一个诚实的正则表达式）。 在我的机器上完成大约需要24秒。