Алгоритм FAST для поиска подстрок в строке

Рабина-Карпа поиск по нескольким шаблонам представляется самым быстрым.

Также проверьте алгоритм Бойера-Мура для сопоставления с одной строкой.

Другим решением является использование массива суффиксов для INSTR .
Поскольку INSTR мало, вы можете сортировать его с помощью пузырьковой сортировки.

После этого вы можете искать определенную строку CAND за время O (logN),
где N = длина (суффикс_array) = длина (INSTR).

import java.util.Scanner;

public class StringMatch 
{
    static int temp,i=0,j=0; static boolean flag=true,matcher=false;

    static String str=null,mstr=null;static char astr[],amstr[];

    static void getter(){
        Scanner sc = new Scanner(System.in);
        str = sc.nextLine();
        //String str="today is Monday"; 
        astr=str.toCharArray();
         mstr = sc.nextLine();
        //String mstr="is"; 
         amstr=mstr.toCharArray();
    }

    static void stringMatch(){
        while(i<astr.length){
            if(astr[i]==amstr[j]){
            while((j!=amstr.length)&&flag){temp=i;
                if(astr[i]!=amstr[j]) {flag=false;matcher=false;}
                else{matcher=true;}
                i++;j++;
                //System.out.println(i+"\t"+j);
            }if(matcher==true)break;i=temp;}i++;j=0;flag=true;

        }
        if(matcher==true) {System.out.println("true");}
        else    {System.out.println("false");}
    }

    public static void main(String[] args) {

    StringMatch.getter();
    StringMatch.stringMatch();

    }
}

Преобразуйте набор строк-кандидатов в детерминированный конечный автомат и затем прогоните входную строку за линейное время. Преобразование одной строки в DFS хорошо описано в стандартных книгах. Вы можете преобразовать набор строк, сначала построив недетерминированный автомат, а затем определив его. В худшем случае это может привести к экспоненциальному увеличению размера автомата, но после этого поиск выполняется быстро; особенно если целевая строка длинная, а кандидаты короткие, это будет хорошо работать.

Это то, для чего нужны регулярные выражения. Как отмечалось выше, конечные автоматы - это то, что вам нужно, но именно так реализован стандартный сопоставитель регулярных выражений.

В java вы можете написать что-то вроде:

StringBuilder sb = new StringBuilder();
bool first = true;
for (String subStr : substrings) {
    if (first)
        first = false;
    else
        sb.append('|');
    sb.append(escape(subStr));
}
Pattern p = Pattern.compile(sb.toString());

метод escape должен экранировать любые символы, которые имеют особое значение в регулярном выражении.

Мы можем воспользоваться преимуществом небольшого размера (<50 символов) строк для создания сверхбыстрого алгоритма для этого случая за счет памяти.

Мы можем хешировать все возможное подстроки INSTR в хеше один раз, что будет стоить O (n ^ 2) раз. Тогда, независимо от количества строк CAND, поиск будет O (1). Стоит для очень большого количества строк CAND.

Если INSTR большой, то мы можем построить массив суффиксов и не сортировать его, так что верхний элемент будет самым длинным (= N), а нижний элемент будет последним символом ИНСТР. Теперь для каждой строки CAND ищите только сверху, пока длина (CAND) <= length (суффикс). Каждое из этих сравнений будет O (n).

Вы можете изучить алгоритм Ахо-Корасика и связанные с ним алгоритмы. Я не знаю ни одной библиотеки, которая бы это реализовала, но это классический способ решения этой проблемы.