Ханойские башни 4 страница

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

Ход работы алгоритма, разделенный на этапы, выглядит следующим образом:

1. зона поиска (на первом шаге ей является весь массив) делиться на две равные части, путем определения ее среднего (mid) элемента;

2. средний элемент сравнивается с искомым (key), результатом этого сравнения будет один из трех случаев:

§ key<mid. Крайней правой границей области поиска становится элемент, стоящий перед средним (right ← mid-1);

§ key>mid. Крайней левой границей области поиска становится следующий за средним элемент (left ← mid+1);

§ key=mid. Значения среднего и искомого элементов совпадают, следовательно элемент найден, работа алгоритма завершается.

3. если для проверки не осталось ни одного элемента, то алгоритм завершается, иначе выполняется переход к пункту 1.

34) Алгоритмы Кнута, Мориса и Пратта

Даны образец (строка) и строка . Требуется определить индекс, начиная с которого образец содержится в строке . Если не содержится в — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Алгоритм Ахо-Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O (| needle |·|Σ|) операций и требует столько же памяти.

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

если haystack[i] = needle[state] то state = state + 1 иначе state = побочный_переход(state, haystack[i])

Легко заметить, что суффиксные ссылки алгоритма Ахо-Корасик представляют собой префикс-функцию искомого шаблона.

Дата добавления: 2015-07-11