Содержание
- 2. План лекции Поиск в массивах и списках Линейный поиск Бинарный поиск Поиск подстроки Наивный поиск подстроки
- 3. Поиск в массивах и списках Значения элементов массива (списка) делятся на ключ и произвольные данные struct
- 4. Последовательный просмотр ячеек Останов, если найден нужный ключ или кончились ячейки Число сравнений в худшем случае
- 5. place_t linear_search (list_t L, K key) { place_t p; for (p = begin(L); p != end();
- 6. Бинарный поиск в упорядоченном массиве На каждом шаге делим массив пополам и на следующем шаге продолжаем
- 7. Бинарный поиск в упорядоченном массиве int binary_search(const struct KeyData A[], int N, K key) { int
- 8. 4 10 17 19 20 28 25 2 33 45 40 42 39 35 46 64
- 9. План лекции Поиск в массивах и списках Линейный поиск Бинарный поиск Поиск подстроки Наивный поиск подстроки
- 10. abcdaaccbbssacbaszzzaaa cbbss s q Поиск подстроки Даны строка s из N элементов (текст) и строка q
- 11. Наивный (прямой) поиск подстроки Шаг 1 «Прикладываем» левый край образца к левому краю текста, К =
- 12. Прямой поиск подстроки int naive_substring_search( const char s[], int N, const char q[], int M) {
- 13. Алгоритм Рабина-Карпа Майкл Рабин р. 1932 Ричард Карп р. 1935 Karp, Richard M. Rabin, Michael O.
- 14. Алгоритм Рабина-Карпа Быстрый поиск нескольких образцов в одном тексте Уменьшение числа сравнений в наивном поиске подстроки
- 15. Алгоритм Рабина-Карпа Шаг 1 Прикладываем левый край образца к левому краю текста, К = 0 Вычисляем
- 16. Алгоритм Рабина-Карпа int rk_substring_search( const char s[], int N, const char q[], int M) { int
- 17. Простая хэш-функция // hs = s[0]+s[1]+…+s[M-1] // чем плоха такая хэш-функция? int rk_hash(const char s[], int
- 18. Улучшенная хэш-функция static const int rk_hash_p = "хорошее" простое число; static const int rk_hash_n = 256;
- 19. Анализ алгоритма Рабина-Карпа Число сравнений зависит от сочетания хэш-функции, текста и образца В худшем случае О((N
- 20. Алгоритм Бойера—Мура Robert Stephen Boyer Роберт Стивен Бойер р. ? J Strother Moore Джей Стротер Мур
- 21. Алгоритм Бойера—Мура Улучшение наивного поиска Сравнение текста и образца, начиная с q[М – 1] и s[k
- 22. Алгоритм Бойера-Мура со сдвигом по стоп-символам Шаг 1 Прикладываем левый край образца к левому краю текста,
- 23. Алгоритм Бойера-Мура без сдвига по суффиксам int bm_substring_search( const char s[], int N, const char q[],
- 24. Заполнение таблицы сдвигов по стоп-символам Для каждого символа x из образца Если q[M-1] != х (не
- 25. Пример заполнения таблицы сдвигов по стоп-символам Для образца q=“аbсаbеаbсе” (М = 10) d['a'] = 3 d['b']
- 26. а friend in need is a friend indeed indeed М = 6 d['i'] = 5 d['n']
- 27. Анализ алгоритма Бойера-Мура В лучшем случае O(N/M) сравнений Если последний символ образца всегда попадает на символ
- 28. Алгоритм Кнута-Морриса- Пратта Donald Knuth Дональд Кнут р. 1938 Воган Пратт р. 1944 Джеймс Моррис р.
- 29. Алгоритм Кнута-Морриса-Пратта Улучшение наивного поиска Каждый символ текста участвует в сравнении Сдвиг выбирается с учётом того,
- 30. Алгоритм Кнута-Морриса-Пратта На сколько позиций можно сдвинуть q относительно s, не пропустив вхождений q в s,
- 31. Префикс-функция КМП Префикс-функция prefix(q, j) строки q prefix(q,j) = max { x | q[0..x] = q[j-x..j],
- 32. Префикс-функция КМП Пример 1 j 0 1 2 3 4 5 6 q[j] a b a
- 33. Алгоритм Кнута-Морриса-Пратта Шаг 1 Прикладываем левый край образца к левому краю окна просмотра, К = 0,
- 34. Алгоритм Кнута-Морриса-Пратта int kmp_substring_search( const char s[], int N, const char q[], int M) { int
- 35. Алгоритм Кнута-Морриса-Пратта В худшем случае О(N) сравнений без учета построения префикс-функции Почему каждый символ текста участвует
- 36. Заключение Поиск в массивах и списках Линейный поиск списки, массивы, линейная сложность Бинарный поиск упорядоч. массивы,
- 37. При первом входе в цикл индексы указывают на начала строк и Eq(i,j) = Eq(1, 1), очевидно,
- 38. При несовпадении очередных символов надо сдвинуть образец так, чтобы некоторый dj-префикс q продолжал совпадать с dj-суффиксом
- 39. До сдвига pref (q, j–1) совпадает с suff (pref (s ,i—1), dj — 1). Чтобы сдвиг
- 40. Добавив теперь условие максимальности длины префикса dj, выразим зависимость dj от j cледующей префикс-функцией: d [j]
- 41. Выбором подходящего dj, с учетом всего сказанного, занимается внутренний цикл КМП-алгоритма. Ниже приведены значения префикс-функции и
- 42. - Eq(i,j): j = 6,d[j] = 4 pref(q,3) = suff(pref(s,i-1),3) d-1 = 3 – длина совпадения
- 43. Допустим, что для всех позиций k образеца, предшествующих и включая i, d[k] уже вычислены и d[i]
- 44. int seek_substring_KMP (char s[], char q[]){ int i, j, N, M; N = strlen(s); M =
- 45. Алгоритм Рабина -- Карпа поиска подстроки Майкл Рабин, Ричард Карп 1987 Уменьшение числа сравнений в наивном
- 46. По схеме Горнера значения tq и t1 можно вычислить за время, пропорциональное М Временно забудем о
- 47. Чтобы получить t[k+1] из t[k], надо удалить последнее слагаемое из формулы (10) ( т. е. вычесть
- 48. Вычислив все tk, мы можем по очереди сравнить их с tq, определив тем самым совпадение или
- 49. Рекуррентная формула (11) приобретает вид: где . Из равенства tq ≡ tk(mod p) еще не следует,
- 50. Алгоритм А5: • вход: q - образец, s - строка, М - длина образеца, N -
- 51. int Robin_Carp_Matcher(char s[], char q[], int d, int p) { int i, h, k, M, N,
- 52. вхождение образца холостое срабатывание … … … (б) mod 13 Цифра старшего разряда Цифра младшего разряда
- 53. Реализация алгоритма Бойера-Мура int seek_substring_BM(unsigned char s[], unsigned char q[]) { int d[256]; int i, j,
- 54. Алгоритм Бойера-Мура Будем последовательно сравнивать образец q с подстроками s[i – М + 1..i] (в начале
- 55. Здесь j = 6 символов строки, следующих за позицией k, уже известны, поэтому можно, не выполняя
- 56. КМП-алгоритм (Кнут, Моррис, Пратт) Алгоритм А4: • вход: q - образец, s - строка, М -
- 57. Индекс-указатель i пробегает строку s без возвратов (что обеспечивает линейность времени работы алгоритма). Индекс j синхронно
- 59. Скачать презентацию