Какой самый быстрый способ поиска подстроки в Java?

Честно говоря, если вы заботитесь о худшем случае, JNI в собственный код, который вызывает вашу стандартную библиотечную функцию strstr. Хорошо реализованная strstr, как и в последних версиях glibc, имеет линейное наихудшее время работы и постоянное использование наихудшего пространства. Я считаю, что glibc strstr может делать Boyer-Moore-подобные длинные прыжки через текст. Стандартные библиотеки C поддерживаются людьми, которые умеют писать и поддерживать хорошие и универсальные библиотеки и практиковать свои ремесла. То же самое нельзя сказать о стандартной библиотеке классов Java.

Вам нужно будет превратить строку Java UTF-16 в нечто подходящее для strstr, например строку UTF-8. Вам также придется обрабатывать встроенные нулевые байты в строке UTF-8 изящно. Помимо этого, вы воспользуетесь преимуществами хорошо написанной и ухоженной библиотеки.

Java выполняет поиск регулярных выражений (для этого конкретного случая) с использованием строкового поиска Boyer-Moore, взломанного в наивную реализацию регулярного выражения. Компиляция Pattern только с вашей строкой приведет к тому, что Matcher будет работать относительно хорошо. Обратите внимание, однако, что это НЕ распространяется на все, кроме поиска строк в библиотеке regex; вы по-прежнему придерживаетесь наивной реализации регулярного выражения, которая отступает и все, если вы кормите это нетривиальное регулярное выражение.

В качестве доказательства того, почему вы не должны использовать регулярное выражение 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 секунд, чтобы завершить работу на моей машине.