Алгоритм поиска строк, который возвращает рекурсивные соответствия - Java

Question

Алгоритм поиска Rabin-Karp работает нормально, но может ли кто-нибудь помочь мне изменить его на рекурсивный поиск? http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html. Например:

* **pattern:** rar 
* **text:** abacadabrararbracabrarararacadabrabrarbracad 
* **match1:**   rar    
* **match2:**   rar 
* **match3:**      rar 
* **match4:**      rar 
* **match5:**       rar 
* **match5:**          rar 

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

РЕШЕНИЕ

Добавить внешнюю библиотеку из http://johannburkard.de/software/stringsearch/ построить путь. Код ниже вернет все начальные позиции совпадений. включая встроенные, такие как match1 и match2.

import com.eaio.stringsearch.BNDM; 

String pattern = "rar"; 
String text = "abacadabrararbracabrarararacadabrabrarbracad"; 

// Loop through text to get starting position of matched pattern. 
List<Integer> matchPoint =new ArrayList<Integer>(); 
int slice = -1; 
while (slice<text.length()){ 
    slice+=1; 
    com.eaio.stringsearch.BNDM result = new BNDM(); 
    int pos = result.searchString(text, slice, pattern); 
    if (pos != -1) { 
     slice = pos; 
     matchPoint.add(pos); 
    } 
} 

Answer 1

Конечно, есть. Я не буду рекомендовать использовать Rabin-Karp в случае поиска небольшого рисунка в строке. KMP i.e алгоритм Кнута-Морриса-Пратта берет линейное время и линейную дополнительную память и может возвращать все матчи без случая столкновения, когда они сталкиваются с Рабином-Карпом. Пожалуйста, прочитайте для него wiki. Этот алгоритм немного сложнее понять, но короче кода, и как только вы это исправите, вы чувствуете себя очень довольным.

Answer 2

Для более длинных узоров Boyer-Moore algorithm или варианты, такие как Horspool's algorithm, как правило, быстрее. Алгоритм Boyer-Moore особенно не подходит для больших алфавитов. Если текст может быть полным диапазоном Юникода, он будет использовать довольно большую таблицу сдвига, но если текст ASCII или latin1, дополнительное пространство для таблиц поиска мало. Для больших алфавитов я также рекомендую KMP.