Содержание
- 2. Суффиксные массивы Пусть задан текст T длины m. Нужно так подготовить текст T, чтобы за минимальное
- 3. Суффиксные массивы . В 1993 году Манбер (Manber U.) и Майерс (Myers G.) предложили для решения
- 4. Суффиксные массивы. Пусть задана m-символьная строка T. Суффиксным массивом для T, обозначенным Pos, называется массив целых
- 5. Пример суффиксов и суффиксного массива для строки «абракадабра».
- 6. Суффиксный массив Суффиксный массиве Pos не занимает много памяти. Огромный плюс суффиксных массивов — их размер
- 7. Построение суффиксного массива Упорядочим суффиксы по первой букве и занесём результат в Pos. Корзиной будем называть
- 8. Построение суффиксного массива Последний суффикс (он же — последний символ строки T) перенесём на первое место
- 9. Поиск образца в строке с помощью суффиксного массива Если образец P входит в строку T, то
- 10. Поиск образца в строке с помощью суффиксного массива Вхождения P в T находим двоичным поиском в
- 11. Поиск образца в строке с помощью суффиксного массива При использовании двоичного поиска в массиве Pos все
- 12. Поиск образца в строке с помощью суффиксного массива Простой ускоритель mlr При двоичном поиске обозначим левую
- 14. Скачать презентацию