Содержание
- 2. Поиск в тексте Задачи, требующие эффективных алгоритмов работы с текстом: работа в текстовом редакторе, поисковые запросы
- 3. Поиск в тексте Задача поиска подстроки в строке Пусть задана строка, состоящая из некоторого количества символов.
- 4. Прямой (последовательный )поиск Данный алгоритм является самым простым и очевидным. Он заключается в посимвольном сравнении текста
- 5. Прямой (последовательный )поиск Алгоритм прямого поиска в тексте
- 6. Прямой (последовательный )поиск //Описание функции прямого поиска подстроки в строке С++ int DirectSearch(char *string, char *substring){
- 7. Прямой (последовательный )поиск Алгоритм работает достаточно эффективно, если несовпадение пары символов происходит после незначительного количества сравнений
- 8. Алгоритм Кнута, Морриса и Пратта Приблизительно в 1970 году Д. Кнут, Д. Моррис и В. Пратт
- 9. Алгоритм Кнута, Морриса и Пратта Если j определяет позицию в слове, содержащую первый несовпадающий символ (как
- 10. Алгоритм Кнута, Морриса и Пратта Пример 1. Текст=‘ABCABCAABCABD’. Слово=‘ABCABD’. 1 шаг. i=1. j=6. suff=‘AB’. shift= j
- 11. Алгоритм Кнута, Морриса и Пратта Замечание: при каждом несовпадении пары символов слово сдвигается на переменную величину,
- 12. Алгоритм Кнута, Морриса и Пратта КМП-алгоритм дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число
- 13. Алгоритм Кнута, Морриса и Пратта Пример 2. Частичное совпадение со словом и вычисление Shift_j. Чем меньше
- 14. Алгоритм Кнута, Морриса и Пратта //Листинг C++ стр.1 //описание функции алгоритма Кнута, Морриса и Пратта С++
- 15. Алгоритм Кнута, Морриса и Пратта //Листинг C++ стр.2 while ( j while ( k >= 0
- 16. Алгоритм Кнута, Морриса и Пратта //Листинг C++ стр.3 i = 0; j = 0; while (
- 17. Алгоритм Боуера и Мура Метод, предложенный Р. Боуером и Д. Муром в 1975 (1977?) году (БМ-алгоритм),
- 18. Алгоритм Боуера и Мура Cравнение символов начинается с конца слова. Пусть обнаружено расхождение между словом и
- 19. Алгоритм Боуера и Мура Пример. Текст=‘ABCAFDFABCABD’. Слово=‘ABCABD’. Shift[‘A’]=2; Shift[‘B’]=1; Shift[‘C’]=3; Shift[‘D’]=0; Shift[‘F’]=6=M, (Shift[x]=6=M, x∈Alf и x∉слову)
- 20. Алгоритм Боуера и Мура Почти всегда, кроме специально построенных примеров, алгоритм требует значительно меньше O(N) сравнений.
- 21. Алгоритм Боуера и Мура //Листинг C++ стр.1 //описание функции алгоритма Бойера и Мура C++ int BMSearch(char
- 22. Алгоритм Боуера и Мура //Листинг C++ стр.2 Pos = ssl - 1; while ( Pos if
- 23. Алгоритм Боуера и Мура Усовершенствование алгоритма Существуют попытки совместить присущую алгоритму Кнута, Морриса и Пратта эффективность
- 24. Алгоритм Боуера и Мура Усовершенствование алгоритма Но дополнительное усложнение формирования таблиц и самого поиска, может не
- 25. Алгоритмы поиска в тексте Алгоритм прямого поиска – это алгоритм поиска подстроки в строке, при котором
- 26. Алгоритмы поиска в тексте Поиск подстрок с помощью конечных автоматов Пример Дана последовательность букв x[1],...,x[n]. Определить,
- 27. Алгоритмы поиска в тексте Читая очередную букву, переходим в следующее состояние по правилу, описанному в таблице:
- 28. Алгоритмы поиска в тексте Программа для примера //поиск подслова "abcd" в заданном слове x var n
- 29. Алгоритм Кнута, Морриса и Пратта Дональд Эрвин Кнут (англ. Donald Ervin Knuth родился 10 января 1938)
- 30. Алгоритм Кнута, Морриса и Пратта В. Пратт (Vaughan Pratt Рональд, род. 1944), заслуженный профессор в Стэнфордском
- 31. Алгоритм Кнута, Мориса и Пратта Джеймс Х. Моррис (р. 1941) является профессором компьютерных наук. Ранее он
- 33. Скачать презентацию