Вопросы

Набор для практики

Краткие итоги

Ключевые термины

Алгоритм Бойера и Мура – это алгоритм поиска подстроки в строке, при котором первоначально строится таблица смещений для искомой подстроки, проверка начинается с последнего символа подстроки после совмещения начала строки и подстроки.

Алгоритм Кнута, Морриса и Пратта – это алгоритм поиска подстроки в строке, при котором сдвиг подстроки выполняется на некоторое переменное количество символов.

Алгоритм прямого поиска – это алгоритм поиска подстроки в строке, при котором происходит посимвольное сравнение строки с подстрокой.

Алфавит – конечное множество символов

Длина строки – количество символов в строке

Подстрока – это последовательность подряд идущих символов в строке.

Префикс– это подстрока, начинающаяся с первого символа строки.

Строка – это последовательность символов.

Суффикс – это подстрока, заканчивающаяся на последний символ строки.

1.Задачи поиска слова в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи и других сферах человеческой деятельности.

2.Основная идея алгоритма прямым поиском заключается в посимвольном сравнении строки с подстрокой.

3.Алгоритм прямого поиска является малозатратным и не нуждается в предварительной обработке и в дополнительном пространстве.

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

5.Трудоемкость алгоритма Кнута, Морриса и Пратта лучше, чем трудоемкость алгоритма прямого поиска.

6.Особенность алгоритма Бойера и Мура заключается в предварительных вычислениях над подстрокой с целью сравнения подстроки с исходной строкой, осуществляемой не во всех позициях.

7.Алгоритм Бойера и Мура оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.

1. Приведите пример входных данных для реализации эффективного метода прямого поиска подстроки в строке.

2. Приведите пример строки, для которой поиск подстроки «aaabaaa» будет более эффективным, если делать его методом Кнута, Морриса и Пратта, чем, если делать его методом Бойера и Мура. И наоборот.

3. Объясните, как влияет размер таблицы кодов в алгоритме Бойера и Мура на скорость поиска.

4. За счет чего в алгоритме Бойера и Мура поиск оптимален в большинстве случаев?

5. Поясните влияние префикс-функции в алгоритме Кнута, Морриса и Пратта на организацию поиска подстроки в строке.