Подстрока

Непрерывная часть последовательности символов

« строка » является подстрокой « подстроки »

В формальной теории языка и информатике подстрока — это непрерывная последовательность символов внутри строки . ^{[ требуется ссылка ]} Например, « the best of » — это подстрока « It was the best of times ». Напротив, « Itwastimes » — это подпоследовательность « It was the best of times », но не подстрока.

Префиксы и суффиксы являются частными случаями подстрок. Префикс строки — это подстрока , которая встречается в начале ; аналогично, суффикс строки — это подстрока , которая встречается в конце . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

Подстроки строки « apple » будут следующими: « a », « ap », « app », « appl », « apple », « p », « pp », « ppl », « pple », « pl », « ple », « l », « le », « e », «» (обратите внимание на пустую строку в конце).

Подстрока

Строка является подстрокой (или фактором) ^[1] строки, если существуют две строки и такие, что . В частности, пустая строка является подстрокой каждой строки. ${\displaystyle u}$ ${\displaystyle t}$ ${\displaystyle p}$ ${\displaystyle s}$ ${\displaystyle t=pus}$

Пример: строка равна подстрокам (и подпоследовательностям) с двумя различными смещениями: ${\displaystyle u=}$ana ${\displaystyle t=}$banana

банан ||||| ана|| ||| ана

Первое вхождение получено с помощью и , а второе вхождение получено с помощью и , являющихся пустой строкой. ${\displaystyle p=}$b ${\displaystyle s=}$na ${\displaystyle p=}$ban ${\displaystyle s}$

Подстрока строки — это префикс суффикса строки и, что эквивалентно, суффикс префикса; например, nanявляется префиксом nana, который в свою очередь является суффиксом banana. Если является подстрокой , то это также подпоследовательность , что является более общей концепцией. Вхождения заданного шаблона в заданную строку можно найти с помощью алгоритма поиска строк . Поиск самой длинной строки, которая равна подстроке двух или более строк, известен как задача о самой длинной общей подстроке . В математической литературе подстроки также называются подсловами (в Америке) или факторами (в Европе). ^{[ необходима цитата ]} ${\displaystyle u}$ ${\displaystyle t}$

Префикс

Строка является префиксом ^[1] строки, если существует строка такая, что . Собственный префикс строки не равен самой строке; ^[2] некоторые источники ^[3] дополнительно ограничивают собственный префикс непустым. Префикс можно рассматривать как особый случай подстроки. ${\displaystyle p}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t=ps}$

Пример: строка banравна префиксу (а также подстроке и подпоследовательности) строки banana:

банан|||запретить

Символ квадратного подмножества иногда используется для обозначения префикса, так что обозначает, что является префиксом . Это определяет бинарное отношение на строках, называемое отношением префикса , которое является особым видом порядка префикса . ${\displaystyle p\sqsubseteq t}$ ${\displaystyle p}$ ${\displaystyle t}$

Суффикс

Строка является суффиксом ^[1] строки, если существует строка такая, что . Собственный суффикс строки не равен самой строке. Более ограниченная интерпретация состоит в том, что он также не пуст. ^[1] Суффикс можно рассматривать как особый случай подстроки. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle p}$ ${\displaystyle t=ps}$

Пример: строка nanaравна суффиксу (а также подстроке и подпоследовательности) строки banana:

банан |||| бабушка

Дерево суффиксов для строки — это структура данных trie , которая представляет все ее суффиксы. Деревья суффиксов имеют большое количество применений в строковых алгоритмах . Массив суффиксов — это упрощенная версия этой структуры данных, которая перечисляет начальные позиции суффиксов в алфавитном порядке; он имеет много тех же применений.

Граница

Граница — это суффикс и префикс одной и той же строки, например, «bab» — ​​это граница «babab» (а также «baboon eating a kebab»). ^{[ необходима цитата ]}

Суперструна

Суперстрока конечного набора строк — это одна строка, которая содержит каждую строку из в качестве подстроки. Например, — суперстрока из , а — более короткая. Конкатенация всех членов из в произвольном порядке всегда дает тривиальную суперстроку из . Нахождение суперстрок, длина которых наименьшая, является более интересной задачей. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle {\text{bcclabccefab}}}$ ${\displaystyle P=\{{\text{abcc}},{\text{efab}},{\text{bccla}}\}}$ ${\displaystyle {\text{efabccla}}}$ ${\displaystyle P}$ ${\displaystyle P}$

Строка, содержащая все возможные перестановки указанного набора символов, называется суперперестановкой .

Смотрите также

• Обозначение скобок
• Индекс подстроки
• Суффиксный автомат

Ссылки

1. Лотер, М. (1997). Комбинаторика слов . Кембридж: Cambridge University Press. ISBN 0-521-59924-5.
2. Келли, Дин (1995). Автоматы и формальные языки: Введение . Лондон: Prentice-Hall International. ISBN 0-13-497777-7.
3. Гасфилд, Дэн (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . США: Cambridge University Press. ISBN 0-521-58519-8.