Обработка символьных массивов

Автор(ы): Айткулов П. Г.

Название статьи: Обработка символьных массивов

Выпуск: 28

Рубрика: Информационные технологии в управлении

Год: 2010

Библиография: Айткулов П. Г. Обработка символьных массивов / Управление большими системами. Выпуск 28. М.: ИПУ РАН, 2010. С.126-178.

Дата опубликования: 31.03.2010

Ключевые слова: алгоритмы на строках, суффиксный массив, наибольшая общая подстрока

Аннотация: Суффиксный массив для строки представляет собой структуру данных, которая позволяет искать все вхождения образца за линейное время от длины образца. Построены алгоритмы модификации суффиксного массива при добавлении одного символа, при добавлении блока к исходной строке и удалении блока из строки. Найдено применение построенных алгоритмов к индексации текстовых записей в базах данных и имен файлов в файловой системе. Построен алгоритм поиска наибольшей общей подстроки для k-строк для динамического случая.

Author(s): Ajtkulov P. G.

Article title: Symbol array processing

Issue: 28

Year: 2010

Keywords: string matching, suffix array, longest common substring

Abstract: Suffix array for a string is a data structure, which allows searching all occurrences of the sample in linear time on the sample length. We build the algorithms for modifying a suffix array by adding one character, by adding blocks to the original string, and by removing the block from the string. We suggest applying these algorithms to index text entries in databases and file names in a file system. We also develop the algorithm for online search of the longest common substring in k-strings.

в формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 7584; загрузок: 3188, за месяц: 11.

Назад