Содержание
- 2. Основная идея Осуществляется полная или частичная обработка входных данных с сохранением полученной дополнительной информации для ускорения
- 3. Основные подходы к решению задачи пространственно-временного компромисса Улучшение входных данных (- метод сортировки подсчетом, - алгоритм
- 4. 4.1. Сортировка подсчетом Основная идея: подсчитать для каждого элемента сортируемого списка общее количество элементов, меньших данного,
- 5. Пример работы алгоритма сортировки подсчетом сравнений Массив A[0..5] | 62 | 31 | 84 | 96
- 6. 4.2. Улучшение входных данных в поиске подстрок Задача поиска подстрок состоит в поиске данной подстроки из
- 7. Алгоритм Хорспула Пример. Поиск подстроки BARBER в некотором тексте: S0 …. …. c ……Sn-1 BARBER Алгоритм
- 8. Случай 1. Если символа с в образце нет, то можно сдвинуть образец на всю его длину.
- 9. Случай 2. Если символ с в образце есть, но он не последний. S0 …. …. B
- 10. Случай 3. Если символ с последний символ образца и среди остальных (m-1) символов образца такого символа
- 11. Случай 4. Если символ с последний символ образца и среди остальных (m-1) символов образца имеются вхождения
- 12. Величины сдвигов для символа с : Длина образца m, если с нет среди первых m-1 символов
- 13. Алгоритм ShiftTable (P[0..m-1]) // Заполнение таблицы сдвигов // Вх. данные: Образец P[0..m-1] и алфавит возможных символов
- 14. Алгоритм Хорспула Шаг 1. Для данного образца длиной m и алфавита, используемого в тексте и образце,
- 15. 1. Начиная с последнего символа образца, сравниваем соответствующие символы в шаблоне и в тексте, пока не
- 16. Алгоритм Horspool (P [0..m-1], T [0..m-1]) // Вх. данные: Образец P [0..m-1], и текст T [0..m-1]
- 18. Скачать презентацию