Высокоскоростные алгоритмы сопоставления строк

Я в основном сравниваю некоторые высокоскоростные алгоритмы соответствия строк, я наткнулся на несколько.

  • Назад Недетерминированный DAWG (Направленный ациклический граф слов) Соответствующий алгоритм Гонсало Наварро и Матье Раффино. См Бит-параллельный подход к суффикс-автоматам: быстрая расширенная строка Matching "

  • Horspool улучшенная версия строки Boyer-Moore алгоритм поиска. См. "Практический быстрый поиск в строках"

  • Сдвиг-алгоритм с несоответствиями

  • KMP

Есть ли другие лучшие алгоритмы высокоскоростного сопоставления строк, которые я могу попробовать?

Изменить: есть еще один поток в похожих строках, который также имеет хорошие ссылки

Ответы

Ответ 1

Вы также можете попробовать

  • Z Алгоритм: В некотором смысле даже более аккуратный, чем KMP
  • Aho Corasick: основанный на Trie и первоначально используемый для fgrep
  • Рабин Карп: Hash based

Ответ 2

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

Если вы знаете, что ваши пользователи не рывками, наивное соответствие строк, оптимизированное для вашей архитектуры, выиграет для коротких "игл", в то время как вариант Boyer-Moore начнет действительно делать сублинейную вещь для длинных "игл". Однако наивное сопоставление строк имеет квадратичный худший случай, и Boyer-Moore может быть сделан для изучения всех символов ввода. Дополнительные таблицы, необходимые для обработки несоответствий, на самом деле имеют удивительно суровое наказание за сопоставление двухсторонней строки.

Ответ 3

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

    }
}