Построение таблицы.

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

· Сканирование слева направо, сравнение - справа налево (совмещается начало текста и шаблона, проверка с последнего символа, если символы совпали – поиск окончен, если какой-то символ не совпадает – шаблон сдвигается на несколько символов вправо и снова начинается проверка)

· Эвристика стоп символа. Эвристика – наука, изучающая несознательное мышление. Эвристический метод – метод наводящих вопросов, рассчитанный на то, что человек или программа самостоятельно найдет ответ на вопрос

· Эвристика совпадающего суффикса – если при сравнении строки и шаблона совпал 1 или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал

Пусть нам необходимо произнести поиск слова «колокол». Пусть первая буква не совпала, назовем данную букву К – стоп символа. Тогда можно сдвинуть шаблон вправо до последней буквы К. Если стоп символа в шаблоне вообще нет, шаблон смещается за этот стоп символ.

Пример:

Строка: *****ал***

Шаблон: колокол

Сл. Шаг: колокол

В данном случае стоп символ А, и шаблон смещается так, чтобы он оказался за этой буквой. В данном алгоритме эвристика не смотрит на совпадающий суффикс, так что К окажется под Л и будет проведена пустая проверка.

Пример:

Строка: **токол***

Шаблон: колокол

Сл. Шаг: колокол

Если при сравнении шаблона и строки, совпал 1 или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал. В данном случае совпал суффикс ОКОЛ, шаблон сдвигается вправо до ближайшего ОКОЛ. Если подстроки ОКОЛ в шаблоне больше нет, но он начинается на КОЛ, шаблон сдвигается до КОЛ.

7. Пусть имеется некий текст T, некое слово или образ W. Необходимо найти данное слово в указанном месте. Элементы массива T и W, символы некоторого конечного алфавита.

{1, … 0}

{a, … z}

{а, … я}

Наиболее типичным является документальный поиск. Поиск строки определяется следующим образом: задан массив T из N элементов и массив W из M элементов, основное условие: 0< M< =N. Поиск строки обнаруживает первое вхождение W в T, результатом будет считаться индекс i, указывающий на первое, с начала массива, совпадение с областью.

Текст T

Образ W

S = 3

I = 4