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

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

Содержание ▲

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

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

Слайд 1

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

Поиск подстрок

Слайд 2

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

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

Слайд 3

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

Пример Дана последовательность символов x[1]..x[n]. Определить, встречаются ли в ней идущие друг за другом символы "abcd". (Другими словами, требуется выяснить, есть ли в слове x[1]..x[n] подслово "abcd".)

Слайд 4

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

Простой алгоритм Решение. Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомое подслово в исходном слове. Для каждой из позиций можно проверить, действительно ли с нее начинается подслово, сравнив четыре символа. Но обычно слово x[1]..x[n] просматривается слева направо, до появления буквы 'a'. Как только она появилась, ищем за ней букву 'b', затем 'c', и, наконец, 'd'. Если ожидания оправдываются, то слово "abcd" обнаружено. Если же какая-то из нужных букв не появляется, начинаем поиск с новой позиции.

Слайд 5

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

Конечные автоматы при чтении слова x слева направо мы в каждый момент находимся в одном из следующих состояний: "начальное" (0), "сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3) и "сразу после abcd" (4). Читая очередную букву, мы переходим в следующее состояние по правилу

Слайд 6

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

Конечные автоматы Читая очередную букву, мы переходим в следующее состояние по правилу: <Текущее состояние> <Очередная буква> <Новое состояние >

Слайд 7

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

Алгоритм состояние буква состояние 0 a 1 0 кроме a 0 1 b 2 1 a 1 1 кроме a,b 0 2 c 3 2 a 1 2 кроме a,c 0 3 d 4 3 a 1 3 кроме a,d 0 Состояние 4 - конечное

Слайд 8

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

Фрагмент программы-1 i=1; state=0; {i - первая непрочитанная буква, state - состояние} while ((i <> n+1) and (state <> 4)) { if (state = =0) { if( x[i] ==‘a’) { state= 1; }

Слайд 9

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

Фрагмент программы-2 else { state= 0; } }else if (state == 1) { if (x[i] == ‘b’) { state= 2; } else if( x[i] == ‘a’) { state= 1; }else

Слайд 10

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

Фрагмент программы-3 { state= 0; } }else if (state == 2) { if (x[i] == ‘c’) { state= 3; }else if (x[i] == ‘a’){ state= 1; } else { state= 0; }

Слайд 11

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

Фрагмент программы-4 } else if (state == 3) { if( x[i] == ‘d’){ state= 4; } else if (x[i] == ‘a’){ state= 1; } else { state= 0; } } } answer = (state == 4);

Слайд 12

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

Усовершенствованный алгоритм Надо написать программу, которая ищет произвольный образец в произвольном слове. Это можно делать в два этапа: 1. сначала по образцу строится таблица переходов конечного автомата 2. читается входное слово и состояние преобразуется в соответствии с этой таблицей

Слайд 13

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

Алгоритм Кнута - Морриса – Пратта (КМП) Работает за время O(m+n), где m – длина образца, n – длина текста Для произвольного слова X рассмотрим все его начала (префиксы), одновременно являющиеся его концами (суффиксами), и выберем из них самое длинное Примеры: l(aba)=a, l(abab)=ab, l(ababa)=aba, l(abc) = пустое слово.

Слайд 14

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

КМП Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки. Префикс –функция заданного образца несет информацию о том, где в образце повторно встречаются различные префиксы образца. Использование этой информации позволяет избежать проверки заведомо недопустимых сдвигов.

Слайд 15

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

π-функция Алгоритм вычисления Символы строк нумеруются с 1. Пусть π(S,i) = k. Попробуем вычислить префикс-функцию для i + 1. Если S[i + 1] = S[k + 1], то, естественно, π(S,i + 1) = k + 1. Если нет — пробуем меньшие суффиксы. Очевидно, что также будет суффиксом строки, а для любого строка суффиксом не будет. Таким образом, получается алгоритм:

Слайд 16

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

π-функция При S[i + 1] = S[k + 1] — положить π(S,i + 1) = k + 1. Иначе при k = 0 — положить π(S,i + 1) = 0. Иначе — установить k: = π(S,k), GOTO 1.

Слайд 17

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

Пример Для строки 'abcdabscabcdabia' вычисление будет таким: 'a'!='b' => π=0;(длина строки 2; строка ab ) 'a'!='c' => π=0; (длина строки 3; строка abс ) 'a'!='d' => π=0;(длина строки 4; строка abcd) 'a'=='a' => π=π+1=1; (длина строки 5; строка abcdа) 'b'=='b' => π=π+1=2;(длина строки 6; строка abcdаb) 'c'!='s' => π=0; (длина строки 6; строка abcdаbs) 'a'!='c' => π=0; (длина строки 7; строка abcdаbsс)

Слайд 18

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

Пример 'a'=='a' => π=π+1=1; (длина строки 8; строка abcdаbsса) 'b'=='b' => π=π+1=2; (длина строки 9; строка abcdаbsсаb) 'c'=='c' => π=π+1=3; (длина строки 9; строка abcdаbsсаbс) 'd'=='d' => π=π+1=4;(длина строки 10; строка abcdаbsсаbсd) 'a'=='a' => π=π+1=5; (длина строки 10; строка abcdаbsсаbсdа) 'b'=='b' => π=π+1=6; (длина строки 11; строка abcdаbsсаbсdаb) ‘s'!='i' => π=0; (длина строки 12; строка abcdаbsсаbсdаbi) 'a'=='a' => π=π+1=1; (длина строки 13; строка abcdаbsсаbсdаbiа)

Слайд 19

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

Пример реализации

Слайд 20

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

Алгоритм с использованием префикс-функции Пусть ищется строка S1 в строке S2. Построим строку S= S1$S2, где $ — символ, не встречающийся ни в S1, ни в S2. Далее вычислим значения префикс-функции от строки S и всех её префиксов. Теперь, если префикс-функция от префикса строки S длины i равна n, где n—длина S1, и i>n, то в строке S2есть вхождение S1, начиная с позиции i-2n.