Поиск подстрок - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ПОИСК ПОДСТРОК

Слайд 2

Описание слайда:

Поиск точно заданной подстроки в строке

Слайд 3

Описание слайда:

В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»).

Слайд 4

Описание слайда:

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0

Слайд 5

Описание слайда:

Пример: Пример: Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca

Слайд 6

Описание слайда:

Идея алгоритма: 1. I=1, 2. сравнить I-й символ массива T с первым символом массива W, 3. совпадение → сравнить вторые символы и так далее, 4. несовпадение → I:=I+1 и переход на пункт 2, Идея алгоритма: 1. I=1, 2. сравнить I-й символ массива T с первым символом массива W, 3. совпадение → сравнить вторые символы и так далее, 4. несовпадение → I:=I+1 и переход на пункт 2, Условие окончания алгоритма: 1. подряд М сравнений удачны, 2. I+M>N, то есть слово не найдено.

Слайд 7

Описание слайда:

Недостатки алгоритма: Недостатки алгоритма: 1. Высокая сложность — O(N*M).

Слайд 8

Описание слайда:

i = –1; //n – длина строки m-подстроки i = –1; //n – длина строки m-подстроки do { i++; j = 0; while((j < m) && (haystack[i + j] == needle[j])) j++; } while ((j != m) && (i < n – m));

Слайд 9

Описание слайда:

Алгоритм Рабина-Карпа (РК-поиск)

Слайд 10

Описание слайда:

ИДЕЯ Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Слайд 11

Описание слайда:

На примере русского алфавита:

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Трудоемкость Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики. В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M). Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.