Определения Пусть задана строка, состоящая из некоторого количества символов. Проверим, входит ли заданная подстрока в данную строку. Если входит, то. - презентация

1

2 Определения

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

4 Основная идея алгоритма прямым поиском заключается в посимвольном сравнении строки с подстрокой. В начальный момент происходит сравнение первого символа строки с первым символом подстроки, второго символа строки со вторым символом подстроки и т. д. Если произошло совпадение всех символов, то фиксируется факт нахождения подстроки. В противном случае производится сдвиг подстроки на одну позицию вправо и повторяется посимвольное сравнение, то есть сравнивается второй символ строки с первым символом подстроки, третий символ строки со вторым символом подстроки и т. д.

5 Символы, которые сравниваются, на рисунке выделены жирным. Рассматриваемые сдвиги подстроки повторяются до тех пор, пока конец подстроки не достиг конца строки или не произошло полное совпадение символов подстроки со строкой, то есть найдется подстрока.

6 //Описание функции прямого поиска подстроки в строке int DirectSearch(char *string, char *substring) { int s1, ss1; //длина строки и подстроки int res = -1; //пока не найдено совпадение s1 = strlen(string); //длина строки ss1 = strlen(substring); //длина подстроки if ( s1 == 0 ) //если строка пустая cout

7 void main() { char str1[100], substr1[100]; //строка и подстрока coutstr1>>substr1; cout

8 Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они совместно опубликовали в 1977 году. Алгоритм Кнута, Морриса и Пратта (КМП -алгоритм) является алгоритмом, который фактически требует только O(n) сравнений даже в самом худшем случае. Рассматриваемый алгоритм основывается на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки фактически известна пройденная часть строки и можно, вычислить некоторые сведения, с помощью которых затем быстро продвинуться по строке. Основным отличием алгоритма Кнута, Морриса и Пратта от алгоритма прямого поиска заключается в том, что сдвиг подстроки выполняется не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Следовательно, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим. Если для произвольной подстроки определить все ее начала, одновременно являющиеся ее концами, и выбрать из них самую длинную (не считая, конечно, саму строку), то такую процедуру принято называть префикс -функцией. В реализации алгоритма Кнута, Морриса и Пратта используется предобработка искомой подстроки, которая заключается в создании префикс -функции на ее основе. При этом используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс.

9 На рисунке символы, подвергшиеся сравнению, выделены жирным шрифтом. Точный анализ рассматриваемого алгоритма весьма сложен. Д. Кнут, Д. Моррис и В. Пратт доказывают, что для данного алгоритма требуется порядка O (m + n) сравнений символов (где n и m – длины строки и подстроки соответственно), что значительно лучше, чем при прямом поиске.

10 //описание функции алгоритма Кнута, Морриса и Пратта int KMPSearch(char *string, char *substring) { int sl, ssl; int res = -1; sl = strlen(string); ssl = strlen(substring); if ( sl == 0 ) cout = 0 && string[i] != substring[j] ) j = d[j]; i++; j++; } delete [] d; res = j == ssl ? i - ssl : -1; } return res; }

11 void main() { char str1[100], substr1[100]; //строка и подстрока cout >str1>>substr1; cout

12 Алгоритм Бойера и Мура считается наиболее быстрым среди алгоритмов, предназначенных для поиска подстроки в строке. Он был разработан Р.Бойером и Д. Муром в 1977 году. Преимущество этого алгоритма в том, что необходимо сделать некоторые предварительные вычисления над подстрокой, чтобы сравнение подстроки с исходной строкой осуществлять не во всех позициях – часть проверок пропускаются как заведомо не дающие результата. Существует множество вариаций алгоритма Бойера и Мура, рассмотрим простейший из них, который состоит из следующих шагов: Первоначально строится таблица смещений для искомой подстроки. Далее идет совмещение начала строки и подстроки и начинается проверка с последнего символа подстроки. Если последний символ подстроки и соответствующий ему при наложении символ строки не совпадают, подстрока сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа подстроки. Если же символы совпадают, производится сравнение предпоследнего символа подстроки и т.д. Если все символы подстроки совпали с наложенными символами строки, значит, найдена подстрока и поиск окончен. Если же какой-то (не последний) символ подстроки не совпадает с соответствующим символом строки, далее производим сдвиг подстроки на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомой подстроки, либо не будет достигнут конец строки.

13 Величина сдвига в случае несовпадения последнего символа вычисляется, исходя из следующего: сдвиг подстроки должен быть минимальным, таким, чтобы не пропустить вхождение подстроки в строке. Если данный символ строки встречается в подстроке, то смещаем подстроку таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в подстроке. Если же подстрока вообще не содержит этого символа, то сдвигаем подстроку на величину, равную ее длине, так что первый символ подстроки накладывается на следующий за проверявшимся символом строки. Величина смещения для каждого символа подстроки зависит только от порядка символов в подстроке, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа подстроки.

14 На рисунке символы, подвергшиеся сравнению, выделены жирным шрифтом. Алгоритм Бойера и Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск. Таким образом, данный алгоритм является наиболее эффективным в обычных ситуациях, а его быстродействие повышается при увеличении подстроки или алфавита. В наихудшем случае трудоемкость рассматриваемого алгоритма O(m + n).

15 //описание функции алгоритма Бойера и Мура int BMSearch(char *string, char *substring) { int sl, ssl; int res = -1; sl = strlen(string); ssl = strlen(substring); if ( sl == 0 ) cout = 0; i-- ){ if ( substring[i] != string[Pos - ssl + i + 1] ) { Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1; break; } else if ( i == 0 ) return Pos - ssl + 1; cout

16 void main() { char str1[100], substr1[100]; //длина строки и подстроки cout >str1>>substr1; cout

17 Задачи поиска слова в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи и др. сферах человеческой деятельности. Основная идея алгоритма прямым поиском заключается в посимвольном сравнении строки с подстрокой. Алгоритм прямого поиска является малозатратным и не нуждается в предварительной обработке и в дополнительном пространстве. Алгоритм Кнута, Морриса и Пратта основывается на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки можно, вычислить сведения, с помощью которых быстро продвинуться по строке. Трудоемкость алгоритма Кнута, Морриса и Пратта лучше, чем трудоемкость алгоритма прямого поиска. Особенность алгоритма Бойера и Мура заключается в предварительных вычислениях над подстрокой с целью сравнения подстроки с исходной строкой, осуществляемой не во всех позициях. Алгоритм Бойера и Мура оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.

18 Задания 1. Строка S была записана много раз подряд, после чего из получившейся строки взяли подстроку и передали как входные данные. Необходимо определить минимально возможную длину исходной строки S. Формат входных данных: В первой и единственной строке входного файла записана строка, которая содержит только латинские буквы, длина строки не превышает символов. Формат выходных данных: В выходной файл нужно вывести одно число – минимально возможную длину исходной строки. Пример входного файла input.txt abababa Пример выходного файла output.txt 2

19 2. Даны две строки a и b. Требуется найти максимальную длину префикса строки a, который входит как подстрока в строку b. При этом считать, что пустая строка является подстрокой любой строки. Формат входных данных В первой строке входного файла содержится строка a, во второй – строка b. Элементами строк a и b являются произвольные символы с кодами ASCII больше 32. Длина каждой строки от 1 до Формат выходных данных: В выходной файл вывести искомую длину префикса строки a, т.е. целое число от 0 до длины строки a. Пример входного файла input.txt abcdefghijklmnopqrstuvwxyz Abcd?aBcd!abCd.abcD!? Пример выходного файла output.txt 3

20 3. Назовем строку палиндромом, если она одинаково читается слева направо и справа налево. Примеры палиндромов: "abcba", "55", "q", "xyzzyx". Требуется для заданной строки найти максимальную по длине ее подстроку, являющуюся палиндромом. Формат входных данных: Во входном файле содержится единственная строка, состоящая из строчных букв латинского алфавита и цифр. Длина строки не превосходит Формат выходных данных: В выходной файл выведите одно целое число - максимальную длину подстроки, являющейся палиндромом. Пример входного файла input.txt a123bc9e9c321 Пример выходного файла output.txt 5

21 Спасибо за внимание