Быстрый алгоритм поиска подстрок в строке

Ответ 1

Прочитайте алгоритм Aho-Corasick и Rabin -Karp алгоритм.

Если вход не слишком велик, вы не хотите повторять поиск много раз, и у вас не так много шаблонов, может быть неплохо использовать один шаблонный алгоритм несколько раз. Статья Википедии об алгоритмах поиска дает множество алгоритмов с временем выполнения и предварительной обработки.

Реализации:

• https://hkn.eecs.berkeley.edu/~dyoo/java/index.html
• http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html
• https://github.com/hankcs/AhoCorasickDoubleArrayTrie
• https://github.com/RokLenarcic/AhoCorasick
• https://github.com/robert-bor/aho-corasick

Презентации:

• http://www.slideshare.net/taka111/ahocorasick-string-matching-algorithm-15078438

Ответ 2

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

Ответ 3

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

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

Ответ 4

Быстрый поиск по шаблону Rabin-Karp является самым быстрым.

Ответ 5

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

Ответ 6

Также проверьте алгоритм Boyer-Moore для однострочного сопоставления строк.

Ответ 7

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

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

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

Ответ 8

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

Впоследствии вы можете найти определенную строку CAND в O (logN),

где N = длина (suffix_array) = длина (INSTR).

Ответ 9

Здесь - некоторая реализация быстрых алгоритмов поиска строк в Java.

Ответ 10

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();

    }
}