Среди алгоритмов поиска совпадений строк двумя наиболее известными являются алгоритм KMP (Кнут-Моррис-Пратт) и алгоритм BM (Бойер-Мур). Оба алгоритма в худшем случае имеют линейное время поиска. Однако на практике алгоритм KMP ненамного быстрее простейшей функции библиотеки C strstr(), тогда как алгоритм BM часто в 3-5 раз быстрее алгоритма KMP (лично не практикуется). Однако алгоритм BM еще не самый быстрый алгоритм. Вот алгоритм поиска, алгоритм Sunday, который быстрее алгоритма BM.
Идея алгоритма Sunday очень похожа на идею плохих персонажей в алгоритме BM. Единственное отличие состоит в том, что после того, как алгоритм Sunday не смог найти совпадение, он занимает символ на одну позицию позади текущей части целевой строки, которая соответствует строке шаблона, чтобы выполнить неправильное сопоставление символов. Когда обнаруживается, что совпадение не удалось, оценивается, существует ли символ с текущим смещением + длина строки шаблона + 1 (предполагается, что это позиция K) в родительской строке в строке шаблона. Если он существует, выровняйте позицию по символу в строке шаблона, а затем сопоставьте его с начала; если он не существует, переместите строку шаблона назад, выровняйте ее по символу k+1 родительской строки, а затем соответствовать. Повторяйте описанную выше операцию до тех пор, пока она не будет найдена или пока не будет найдена родительская строка. Я написал небольшой пример для реализации следующего алгоритма.
В коде реализованы два алгоритма сопоставления строк: один — метод воскресенья, а другой — обычный метод побитового перемещения. Сравнение эффективности этих двух показано в основной функции, оба на наносекундном уровне. . Подробные шаги алгоритма дополнены соответствующими комментариями в коде. Что касается алгоритма БМ, мы вместе сравним и проанализируем в следующий раз, когда он будет пуст.
Скопируйте код кода следующим образом:
импортировать java.util.HashMap;
импортировать java.util.LinkedList;
импортировать java.util.List;
импортировать java.util.Map;
/**
* @автор Скотт
* @дата: 28 декабря 2013 г.
* @описание
*/
общественный класс SundySearch {
Строковый текст = ноль;
Строковый шаблон = ноль;
ИНТ CurrentPos = 0;
/**
* Список позиций первых символов совпавшей подстроки.
*/
List<Integer> matchedPosList = новый LinkedList<Integer>();
/**
* Карта совпадающих символов, записывает, какие символы находятся в соответствующей строке, и последнее смещение каждого символа.
*/
Map<Character, Integer> map = new HashMap<Character, Integer>();
public SundySearch (текст строки, шаблон строки) {
this.text = текст;
this.pattern = шаблон;
это.initMap();
};
/**
* При сопоставлении воскресенья используется для сохранения последней позиции каждого символа в шаблоне, в порядке слева направо.
*/
частная пустота initMap() {
for (int i = 0; i <pattern.length(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* Обычное рекурсивное сопоставление строк: если совпадение не удалось, переместите вперед на одну позицию.
*/
публичный список<Integer>normalMatch() {
//Не удалось найти совпадение, продолжаем опускаться вниз
если (!matchFromSpecialPos(currentPos)) {
ТекущееПос += 1;
if ((text.length() - currentPos) < шаблон.длина()) {
вернуть matchedPosList;
}
нормальное совпадение();
} еще {
//Сопоставление успешно, запись местоположения
matchedPosList.add(currentPos);
ТекущееПос += 1;
нормальное совпадение();
}
вернуть matchedPosList;
}
/**
* Сопоставление по воскресеньям, при условии, что позиция символа K в тексте равна: текущее смещение + длина строки шаблона + 1.
*/
public List<Integer> sundayMatch() {
// Если ни одно совпадение не было успешным
если (!matchFromSpecialPos(currentPos)) {
// Если символ K в тексте не отображается в строке шаблона, пропустите всю длину строки шаблона.
if ((currentPos + шаблон.длина() + 1) < text.length()
&& !map.containsKey(text.charAt(currentPos + шаблон.длина() + 1))) {
currentPos += шаблон.длина();
}еще {
// Если символ K в тексте появляется в строке шаблона, выровняйте положение символа K в тексте с позицией последнего символа K в строке шаблона.
if ((currentPos + шаблон.длина() + 1) > text.length()) {
ТекущееПос += 1;
} еще {
currentPos += шаблон.длина() - (Целое число) map.get(text.charAt(currentPos + шаблон.длина()));
}
}
// Когда совпадение завершено, возвращаем начальное смещение всех успешных совпадений.
if ((text.length() - currentPos) < шаблон.длина()) {
вернуть matchedPosList;
}
воскресеньеМатч();
}еще {
//Если совпадение прошло успешно, переместимся вперед на один бит и затем сопоставим еще раз
matchedPosList.add(currentPos);
ТекущееПос += 1;
воскресеньеМатч();
}
вернуть matchedPosList;
}
/**
* Проверьте, соответствует ли подстрока, начинающаяся с указанного смещения текста, шаблону.
*/
public boolean matchFromSpecialPos(int pos) {
if ((text.length()-pos) < шаблон.длина()) {
вернуть ложь;
}
for (int i = 0; i <pattern.length(); i++) {
if (text.charAt(pos + i) == шаблон.charAt(i)) {
если (я == (pattern.length()-1)) {
вернуть истину;
}
продолжать;
} еще {
перерыв;
}
}
вернуть ложь;
}
public static void main(String[] args) {
SundySearch sundySearch = new SundySearch("привет, ах, Адольф adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");
длинное начало = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - начало));
начало = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - начало));
}
}