Подстрока
В теории формального языка и информатике подстрока представляет собой непрерывную последовательность символов внутри строки . [ нужна ссылка ] Например, « лучшее из » является подстрокой « Это были лучшие времена ». Напротив, « Itwastimes » является подпоследовательностью « It was the best of times », а не подстрокой.
Префиксы и суффиксы — это частные случаи подстрок. Префикс строки является подстрокой что происходит в начале ; аналогично, суффикс строки это подстрока, которая находится в конце .
Подстроки строки « яблоко » будут такими: « а », « ап », « приложение », « приложение », « яблоко », « п », « пп », « пппл », « пппл », " пл ", " пле ", « л », « ле » " е ", "" (обратите внимание на пустую строку в конце).
Подстрока
[ редактировать ]Строка является подстрокой (или фактором) [1] веревки если существует две строки и такой, что . В частности, пустая строка является подстрокой каждой строки.
Пример: строка ana
равно подстрокам (и подпоследовательностям) banana
с двумя разными смещениями:
banana ||||| ana|| ||| ana
Первое вхождение получается с помощью b
и na
, а второе вхождение получается с помощью ban
и пустая строка.
Подстрока строки является префиксом суффикса строки и, что эквивалентно , суффиксом префикса; например, nan
является префиксом nana
, который, в свою очередь, является суффиксом banana
. Если является подстрокой , это также подпоследовательность , которая является более общим понятием. Вхождения данного шаблона в данную строку можно найти с помощью алгоритма поиска строк . Поиск самой длинной строки, которая равна подстроке из двух или более строк, известен как задача о самой длинной общей подстроке .
В математической литературе подстроки также называют подсловами (в Америке) или факторами (в Европе). [ нужна ссылка ]
Префикс
[ редактировать ]Строка это префикс [1] веревки если существует строка такой, что . Правильный префикс строки не равен самой строке; [2] некоторые источники [3] кроме того, ограничьте, чтобы правильный префикс был непустым. Префикс можно рассматривать как частный случай подстроки.
Пример: строка ban
равен префиксу (а также подстроке и подпоследовательности) строки banana
:
banana ||| ban
Символ квадратного подмножества иногда используется для обозначения префикса, так что означает, что является префиксом . Это определяет бинарное отношение к строкам, называемое префиксным отношением , которое представляет собой особый вид префиксного порядка .
Суффикс
[ редактировать ]Строка это суффикс [1] веревки если существует строка такой, что . Правильный суффикс строки не равен самой строке. Более ограниченная интерпретация состоит в том, что он также не пуст. [1] Суффикс можно рассматривать как частный случай подстроки.
Пример: строка nana
равен суффиксу (а также подстроке и подпоследовательности) строки banana
:
banana |||| nana
Суффиксное дерево для строки — это дерева структура данных , которая представляет все ее суффиксы. Суффиксные деревья имеют большое количество приложений в строковых алгоритмах . Массив суффиксов представляет собой упрощенную версию этой структуры данных, в которой перечислены начальные позиции суффиксов в алфавитном порядке; у него много одинаковых приложений.
Граница
[ редактировать ]Граница — это суффикс и префикс одной и той же строки, например «баб» — это граница слова «бабаб» (а также «бабуин, поедающий шашлык»). [ нужна ссылка ]
Суперструна
[ редактировать ]Суперструна множества конечного строк — это одна строка, содержащая каждую строку в как подстрока. Например, представляет собой суперстроку , и является более коротким. Объединение всех членов в произвольном порядке всегда получает тривиальную суперстроку . Найти суперструны минимально возможной длины — более интересная задача.
Строка, содержащая все возможные перестановки указанного набора символов, называется суперперестановкой .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с Лотер, М. (1997). Комбинаторика слов . Кембридж: Издательство Кембриджского университета. ISBN 0-521-59924-5 .
- ^ Келли, Дин (1995). Автоматы и формальные языки: Введение . Лондон: Prentice-Hall International. ISBN 0-13-497777-7 .
- ^ Гасфилд, Дэн (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . США: Издательство Кембриджского университета. ISBN 0-521-58519-8 .