Подстрока

"нить"является подстрокой"подстрока"

В формальная теория языка и Информатика, а подстрока является непрерывной последовательностью символы в пределах нить. Например, "лучший из"является подстрокой"Это были лучшие времена". Это не следует путать с подпоследовательность, который является обобщение подстроки. Например, "Это время"является подпоследовательностью"Это были лучшие времена", но не подстроку.

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

Список всех подстрок строки "яблоко" было бы "яблоко", "приложение", "pple", "приложение", "человек", "Ple", "ap", "pp", "pl", "ле", "а", "п", "л", "е", "" (Обратите внимание пустой строкой в конце).

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

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

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

Первое вхождение получается с ${ displaystyle p =}$ б и ${ displaystyle s =}$ на, а второе вхождение получается с ${ displaystyle p =}$ запретить и ${ displaystyle s}$ это пустая строка.

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

Префикс

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

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

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

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

Суффикс

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

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

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

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

Граница

Граница - это суффикс и префикс одной и той же строки, например. «баб» - это граница «бабаб» (а также «бабунингакебаб»).

Суперструна

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

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

внешняя ссылка

СМИ, связанные с Подстрока в Wikimedia Commons

[Lot97-1] а ^б ^c Лотэр, М. (1997). Комбинаторика слов. Кембридж: Издательство Кембриджского университета. ISBN 0-521-59924-5.

[Kel95-2] Келли, Дин (1995). Автоматы и формальные языки: введение. Лондон: Prentice-Hall International. ISBN 0-13-497777-7.

[Gus97-3] Гасфилд, Дэн (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология. США: Издательство Кембриджского университета. ISBN 0-521-58519-8.

[1]

[2]

[3]

[1]

Подстрока - Substring

Содержание