Comments 19
Не стоит использовать Map для хранения отображения [0, 255] в int, хватило бы простого массива.
А вы знаете, как проиндексировать массив Char'ами? Просто я не знаю как это сделать, поэтому и написал через отображение, что кстати весьма наглядно.
Хотя согласен, можно было хранить инты, а в char преобразовывать тогда, когда нужно. У этого подхода есть и минус — при анализе огромного текста приведение к char будет на каждом шаге цикла. А здесь оно выполняется ровно 256 раз.
Любой приведение такого рода, даже, если оно действительно превратится в машинные инструкции — ничто, по сравнению с поиском в красно-черном дереве. Если вам все еще интересно, рекомендую написать stress test. Если будет меньше двукратного выигрыша по скорости, буду удивлен.
1 Приведение типа (да еще базового) должна быть гораздо более быстрая операция, чем взятие элемента дерева.
2 В общем случае мы работаем в Юникоде, особенно на это намекает ваше «Введите начальную строку» на русском. не говоря уже о том, что это стандарт в Java. Так что 255-ю символами тут никак не обойдешься — минимум 2 байта на символ.
2 В общем случае мы работаем в Юникоде, особенно на это намекает ваше «Введите начальную строку» на русском. не говоря уже о том, что это стандарт в Java. Так что 255-ю символами тут никак не обойдешься — минимум 2 байта на символ.
Эм. (int)c + 127?
Кстати в GNU grep тоже Бойер-Мур используется. Тут автор пишет еще об используемых там способах.
Раз приветствуются любые замечания, то есть парочка по java (К алгоритму замечаний нет)
В методе main() вызываем run(), в run() вызываем finder().
Похоже на отделение реализации алгоритма (поиска) от ввода данных. Ан нет — finder начинается с ввода данных с консоли. Смысл такой реализации остается для меня загадкой (похоже что было портирование алгоритма с другого языка).
В методе main() вызываем run(), в run() вызываем finder().
Похоже на отделение реализации алгоритма (поиска) от ввода данных. Ан нет — finder начинается с ввода данных с консоли. Смысл такой реализации остается для меня загадкой (похоже что было портирование алгоритма с другого языка).
Не было портирования, зато был копипаст элементарной заготовки для написания кода :-)
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.TreeMap;
public class ClassName {
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.TreeMap;
public class ClassName {
Scanner in;
PrintWriter out;
void run() {
in = new Scanner(System.in);
out = new PrintWriter(System.out, true);
try {
//some actions
} finally {
out.close();
}
}
public static void main(String args[]) {
new ClassName().run();
}
}
Пожалуй, всё-таки лучше сделать метод, который возвращает позицию первого вхождения. Сейчас исправлю.
Если последние символы совпадают, то сравнение идет по предпоследнему символу и так далее. Если же символы не совпали, то шаблон смещается вправо, на число позиций взятое из таблицы смещений для символа из исходной строки,
Неверно — таблица смещений работает только для последних несовпавших символов.
А в этом случае — надо либо использовать модифицированную таблицу смещения с поиском несовпавшего символа в строке в шаблоне, либо «для упрощения» сдвигать на 1.
Поясню на примере: в строке ищем aabaaaaa шаблон abaa — таблица смещений
a => 0
b => 2
Сравниваем с конца и видим, что предпоследние символы не совпадают:
aabaaaaa
abaa
Находим по таблице смещений значение сдвига для b — 2, смещаем на 2 позиции и не находим искомой строки.
В написанном исходнике такая же бага.
Было бы понятнее для новичков если в искомой строке символы некоторые повторялись.
Sign up to leave a comment.
Упрощенный алгоритм Бойера-Мура