Упрощенный алгоритм Бойера-Мура

[@DenPlusPlus]

Не стоит использовать Map для хранения отображения [0, 255] в int, хватило бы простого массива.

[@Tibr]

А вы знаете, как проиндексировать массив Char'ами? Просто я не знаю как это сделать, поэтому и написал через отображение, что кстати весьма наглядно.

[@Tibr]

Хотя согласен, можно было хранить инты, а в char преобразовывать тогда, когда нужно. У этого подхода есть и минус — при анализе огромного текста приведение к char будет на каждом шаге цикла. А здесь оно выполняется ровно 256 раз.

[@DenPlusPlus]

Любой приведение такого рода, даже, если оно действительно превратится в машинные инструкции — ничто, по сравнению с поиском в красно-черном дереве. Если вам все еще интересно, рекомендую написать stress test. Если будет меньше двукратного выигрыша по скорости, буду удивлен.

[@Tibr]

Ну, а если бы Hash?

[@leventov]

Тоже самое приведение и получится.

public int hashCode() {
        return (int)value;
}

[@general]

1 Приведение типа (да еще базового) должна быть гораздо более быстрая операция, чем взятие элемента дерева.
2 В общем случае мы работаем в Юникоде, особенно на это намекает ваше «Введите начальную строку» на русском. не говоря уже о том, что это стандарт в Java. Так что 255-ю символами тут никак не обойдешься — минимум 2 байта на символ.

[@Tibr]

По 2: Естественно, если Вы хотите можете написать заполнение всем Unicode'ом, здесь главное было показать принцип заполнения таблицы смещений.

[@DenPlusPlus]

Эм. (int)c + 127?

[@hellman]

Кстати в GNU grep тоже Бойер-Мур используется. Тут автор пишет еще об используемых там способах.

[@general]

Раз приветствуются любые замечания, то есть парочка по java (К алгоритму замечаний нет)

В методе main() вызываем run(), в run() вызываем finder().
Похоже на отделение реализации алгоритма (поиска) от ввода данных. Ан нет — finder начинается с ввода данных с консоли. Смысл такой реализации остается для меня загадкой (похоже что было портирование алгоритма с другого языка).

[@Tibr]

Не было портирования, зато был копипаст элементарной заготовки для написания кода :-)
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();
	}
}

[@Tibr]

Пожалуй, всё-таки лучше сделать метод, который возвращает позицию первого вхождения. Сейчас исправлю.

[@QoSyS]

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

Неверно — таблица смещений работает только для последних несовпавших символов.

А в этом случае — надо либо использовать модифицированную таблицу смещения с поиском несовпавшего символа в строке в шаблоне, либо «для упрощения» сдвигать на 1.

Поясню на примере: в строке ищем aabaaaaa шаблон abaa — таблица смещений
a => 0
b => 2
Сравниваем с конца и видим, что предпоследние символы не совпадают:
aabaaaaa
abaa
Находим по таблице смещений значение сдвига для b — 2, смещаем на 2 позиции и не находим искомой строки.

В написанном исходнике такая же бага.

[@Tibr]

Вы не поверите, но код работает на Вашем примере :-)
Символ-то берется i-й.

[@QoSyS]

да, согласен, все правильно, в упрощенном варианте так можно делать,
создание трех переменных подряд немного сбило столку )

кстати, большой + за форматирование кода.

[@Tibr]

Ничего, бывает :-)

[@Tibr]

Эм. Всё работает, проверьте еще разок.

[@xiWera]

Было бы понятнее для новичков если в искомой строке символы некоторые повторялись.