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

Прочитав статью об алгоритмах поиска подстроки в строке, я обнаружил, что там не рассказывается об алгоритме Бойера-Мура. Пара слов о нём всё-таки там есть, а именно, говорится, что алгоритм Бойера-Мура заслужил себе звание «алгоритма по умолчанию», потому что он в среднем дает лучшее время поиска (с чем я полностью согласен). Под катом рассказано об упрощенной версии этого алгоритма. В принципе, большинство скорее всего изучало этот алгоритм на 1-м или 2-м курсе ВУЗа (как и я), поэтому они могут пропустить эту статью, ничего нового тут нет.

Алгоритм

Данный алгоритм также известен под названием алгоритм Бойера-Мура-Хорспула. Процедура алгоритма очень простая. Сначала строится таблица смещений для каждого символа. Затем исходная строка и шаблон совмещаются по началу, сравнение ведется по последнему символу. Если последние символы совпадают, то сравнение идет по предпоследнему символу и так далее. Если же символы не совпали, то шаблон смещается вправо, на число позиций взятое из таблицы смещений для символа из исходной строки, и тогда снова сравниваются последние символы исходной строки и шаблона. И так далее, пока не шаблон полностью не совпадет с подстрокой исходной строки, или не будет достигнут конец строки.

Таблица смещений

Таблица смещений строится по принципу «пропускать столько символов, сколько возможно, но не более этого». Например, если на каком-то шаге алгоритма последние символы не совпали, и символ, находящийся в исходной строке не присутствует в шаблоне вообще, то понятно, что можно сдвинуться вправо на полную длину шаблона, без каких-либо опасений. В общем случае, каждому символу ставится в соответствие величина, равная разности длины шаблона и порядкового номера символа (если символ повторяется, то берется самое правое вхождение). Ясно, что эта величина будет в точности равна порядковому номеру символа, если считать от конца строки, что и дает возможность смещаться вправо на максимально возможное число позиций.

Иллюстрация

Чтобы стало совсем понятно рассмотрим работу алгоритма на примере:
Пусть исходная строка равна «somestring» и шаблон равен «string». Теперь строим таблицу смещений, она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона):

s->5
t->4
r->3
i->2
n->1
g->6

Теперь совмещаем наши строки:
&nbsp somestring
&nbsp string

Сравниваем последние символы: видим, что «t» не равен «g». Берем значение смещения для символа «t», оно равно 4. Сдвигаем строку вправо на 4 позиции, и вуаля:

&nbsp somestring
&nbsp&nbsp&nbsp&nbsp&nbsp string

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

Код

Написал немного кода на Java, чтобы сдобрить эту теорию. Любые замечания приветствуются.

/**
 * Возвращает индекс первого вхождения строки template в строку source, или
 * -1, в случае если вхождение не найдено.
 * 
 * @param source
 *            исходная строка, в которой ищется вхождение шаблона.
 * @param template
 *            шаблон строки, которая ищется в строке source.
 * @return индекс первого вхождения строки template в строку source, или -1,
 *         в случае если вхождение не найдено.
 */
public int getFirstEntry(String source, String template) {
	int sourceLen = source.length();
	int templateLen = template.length();
	if (templateLen > sourceLen) {
		return -1;
	}
	HashMap<Character, Integer> offsetTable = new HashMap<Character, Integer>();
	for (int i = 0; i <= 255; i++) {
		offsetTable.put((char) i, templateLen);
	}
	for (int i = 0; i < templateLen - 1; i++) {
		offsetTable.put(template.charAt(i), templateLen - i - 1);
	}
	int i = templateLen - 1;
	int j = i;
	int k = i;
	while (j >= 0 && i <= sourceLen - 1) {
		j = templateLen - 1;
		k = i;
		while (j >= 0 && source.charAt(k) == template.charAt(j)) {
			k--;
			j--;
		}
		i += offsetTable.get(source.charAt(i));
	}
	if (k >= sourceLen - templateLen) {
		return -1;
	} else {
		return k + 1;
	}
}

Заключение

Говорят, что такая модификация алгоритма Бойера-Мура справляется со случайными текстами лучше, чем сам исходный алгоритм. Однако, оценка сложности в худшем случае у него всё-таки похуже. Но в отличии от исходного алгоритма, здесь не требуется никаких сложных вычислений — строится только таблица смещений, что не так сложно для реализации.