Поиск подстроки в строке осуществляется по заданному образцу, т.е. некоторой последовательности символов, длина которой не превышает длину исходной строки. Задача поиска заключается в том, чтобы определить, содержит ли строка заданный образец и указать место (индекс) в строке, если совпадение найдено.
Алгоритм грубой силы является самым простым и самым медленным и заключается в проверке всех позиций текста на предмет совпадения с началом образца. Если начало образца совпадает, то сравнивается следующая буква в образце и в тексте и так далее додавниваетсямым простым и самым медленным иостого ответа, есть или нет такого элемента без указания инде уже отсортирован по неу полного совпадения образца или отличия в очередной букве.
int BFSearch(char *s, char *p)
for (int i = 1; strlen(s) - strlen(p); i++)
for (int j = 1; strlen(p); j++)
if (p[j] != s)
if (j = strlen(p))
Функция BFSearch ищет подстроку p в строке s и возвращает индекс первого символа подстроки или 0, если подстрока не найдена. Хотя в общем случае этот метод, как и большинство методов грубой силы, малоэффективен, в некоторых ситуациях он вполне приемлем.
Наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке, считается алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), суть которого в следующем.
Алгоритм Бойера-Мура
Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге строится таблица смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т.д. Если все символы образца совпали с наложенными символами строки, значит найдена подстрока и поиск окончен. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, мы сдвигаем образец на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.
Величина сдвига в случае несовпадения последнего символа вычисляется по правилу: сдвиг образца должен быть минимальным, таким, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, то смещается образец таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце. Если же образец вообще не содержит этого символа, то образец сдвигается на величину, равную его длине, так что первый символ образца накладывается на следующий за проверявшимся символом строки.
Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Поясним все вышесказанное на простом примере. Пусть есть набор из пяти символов: a, b, c, d, e и нужно найти вхождение образца “abbad” в строке “abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполнения алгоритма:
Таблица смещений для образца “abbad”.
Начало поиска. Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций:
Три символа образца совпали, а четвертый – нет. Сдвигаем образец вправо на одну позицию:
Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 2 позиции:
Еще раз сдвигаем образец на 2 позиции:
Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:
Реализуем указанный алгоритм. Прежде всего, следует определить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256 символов, определение структуры будет выглядеть так:
BMTable MakeBMTable(char *p)
for (i = 0; i <= 255; i++) bmt->bmtarr[i] = strlen(p);
for (i = strlen(p); i <= 1; i--)
if (bmt->bmtarr] == strlen(p))
bmt->bmtarr] = strlen(p)-i;
Теперь напишем функцию, осуществляющую поиск.
int BMSearch(int startpos, char *s, char *p)
pos = startpos + lp - 1;
while (pos < strlen(s))
if (p != s) pos = pos + bmt->bmtarr];
for (i = lp - 1; i <= 1; i--)
if (p[i] != s)
return(pos - lp + 1);
Функция BMSearch возвращает позицию первого символа первого вхождения образца p в строке s. Если последовательность p в s не найдена, функция возвращает 0. Параметр startpos позволяет указать позицию в строке s, с которой следует начинать поиск. Это может быть полезно в том случае, если вы захотите найти все вхождения p в s. Для поиска с самого начала строки следует задать startpos равным 1. Если результат поиска не равен нулю, то для того, чтобы найти следующее вхождение p в s, нужно задать startpos равным значению «предыдущий результат плюс длина образца».
Бинарный (двоичный) поиск
Бинарный поиск используется в том случае, если массив, в котором осуществляется поиск, уже упорядочен.
Переменные lb и ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный элемент. Поиск начинается всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, то нужно перейти к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением ub становится (m – 1) и на следующей итерации проверяется половина исходного массива. Таким образом, в результате каждой проверки вдвое сужается область поиска. Например, если в массиве 100 чисел, то после первой итерации область поиска уменьшается до 50 чисел, после второй – до 25, после третьей до 13, после четвертой до 7 и т.д. Если длина массива равна n, то для поиска в массиве элементов достаточно около log 2 n сравнений.
и следующую функцию: function show(pos, path, w, h) { var canvas = document.getElementById("canID"); // получаем объект канваса var ctx = canvas.getContext("2d"); // у него есть свойство - контекст рисования var x0 = 10, y0 = 10; // положение левого верхнего угла карты canvas.width = w+2*x0; canvas.height = h+2*y0; // меняем размеры канваса (чуть больше, чем w x h) ctx.beginPath(); // начало рисования ломаной линии ctx.moveTo(x0+pos.x,y0+pos.y)// переходим на 0-й город for(var i=1; i Пример результата вызова функции приведен справа. Смысл команд рисования должен быть ясен из их названия и комментариев в коде. Сначала рисуется замкнутая ломаная линия (путь коммивояжёра). Затем - окружности городов и поверх них - номера городов. Работа с канавасом в JavaScript несколько громоздка и в дальнейшем мы будем использовать класс draw , который эту работу упрощает и одновременно позволяет получать картинки в svg-формате.
Реализация переборного алгоритма поиска кратчайшего пути в таймере не представляет труда. Для сохранения лучшего пути в массиве minWay , напишем функцию копирования значений элементов массива src в массив des :
Function copy(des, src) { if(des.length !== src.length) des = new Array(src.length); for(var i=0; i
Метод грубой силы представляет собой прямой подход к решению
задачи, обычно основанный непосредственно на формулировке задачи и определениях используемых ею концепций.
Алгоритм, основанный на методе грубой силы, для решения общей задачи поиска называется последовательным поиском. Этот алгоритм просто по очереди сравнивает элементы заданного списка с ключом поиска до тех пор, пока не будет найден элемент с указанным значением ключа (успешный поиск) или весь список будет проверен, но требуемый элемент не найден (неудачный поиск). Зачастую применяется простой дополнительный прием: если добавить ключ поиска в конец списка, то поиск обязательно будет успешным, следовательно, можно убрать проверку завершения списка в каждой итерации алгоритма. Далее приведен псевдокод такой улучшенной версии; предполагается, что входные данные имеют вид массива.
Если исходный список отсортирован, можно воспользоваться еще одним усовершенствованием: поиск в таком списке можно прекращать, как только встретится элемент, не меньший ключа поиска. Последовательный поиск представляет превосходную иллюстрацию метода грубой силы, с его характерными сильными (простота) и слабыми (низкая эффективность) сторонами.
Совершенно очевидно, что время работы этого алгоритма может отличаться в очень широких пределах для одного и того же списка размера п. В наихудшем случае, т.е. когда в списке нет искомого элемента либо когда искомый элемент расположен в списке последним, в алгоритме будет выполнено наибольшее количество операций сравнения ключа со всеми n элементами списка: C(n) = n.
Алгоритм Рабина представляет собой модификацию линейного алгоритма, он основан на весьма простой идее:
«Представим себе, что в слове A, длина которого равна m, мы ищем образец X длины n. Вырежем "окошечко" размером n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины n, тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.»
Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма.
Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются наиболее оптимальными.
Метод КМП использует предобработку искомой строки, а именно: на ее основе создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.
