🗊Презентация Поиск подстрок

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Поиск подстрок, слайд №1Поиск подстрок, слайд №2Поиск подстрок, слайд №3Поиск подстрок, слайд №4Поиск подстрок, слайд №5Поиск подстрок, слайд №6Поиск подстрок, слайд №7Поиск подстрок, слайд №8Поиск подстрок, слайд №9Поиск подстрок, слайд №10Поиск подстрок, слайд №11Поиск подстрок, слайд №12Поиск подстрок, слайд №13Поиск подстрок, слайд №14Поиск подстрок, слайд №15Поиск подстрок, слайд №16
Скачать
Вы можете ознакомиться и скачать презентацию на тему Поиск подстрок. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


ПОИСК ПОДСТРОК
Описание слайда:
ПОИСК ПОДСТРОК

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


Пример: Пример: Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca
Описание слайда:
Пример: Пример: Требуется найти все вхождения образца 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, то есть слово не найдено.
Описание слайда:
Идея алгоритма: 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).
Описание слайда:
Недостатки алгоритма: Недостатки алгоритма: 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));
Описание слайда:
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│.
Описание слайда:
ИДЕЯ Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Слайд 11


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

Слайд 12


Поиск подстрок, слайд №12
Описание слайда:

Слайд 13


Поиск подстрок, слайд №13
Описание слайда:

Слайд 14


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

Слайд 15


Пример: Сколько холостых срабатываний k сделает алгоритм РК, если  q= 11, 13, 17. Пусть W={2 6}
Описание слайда:
Пример: Сколько холостых срабатываний k сделает алгоритм РК, если  q= 11, 13, 17. Пусть W={2 6}

Слайд 16


Поиск подстрок, слайд №16
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию