Подстрока

« строка » - это подстрока « подстроки »

В формальной теории языка и информатики , подстрока представляет собой непрерывную последовательность символов в строке . Например, « лучшее из » - это подстрока « Это были лучшие времена ». Это не следует путать с подпоследовательностью , которая является обобщением подстроки. Например, « Itwastimes » - это подпоследовательность « Это были лучшие времена », но не подстрока.

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

Список всех подстрок строки « яблоко » будет « яблоко », « заявл », « pple », « приложение », « PPL », « PLE », « ап », « с », « пл », " le "," a "," p "," l "," e "," "(обратите внимание на пустую строку в конце).

Подстрока [ править ]

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

Пример: строка равна подстрокам (и подпоследовательностям) из двух разных смещений: ${\ 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}$ $t=ps$

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

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

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

Суффикс [ править ]

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

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

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

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

Граница [ править ]

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

Суперструна [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

^ a b c Лотэр, М. (1997). Комбинаторика слов . Кембридж: Издательство Кембриджского университета. ISBN 0-521-59924-5.
^ Келли, Дин (1995). Автоматы и формальные языки: введение . Лондон: Prentice-Hall International. ISBN 0-13-497777-7.
^ Gusfield, Dan (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . США: Издательство Кембриджского университета. ISBN 0-521-58519-8.

Внешние ссылки [ править ]

СМИ, связанные с подстрокой, на Викискладе?

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

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

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

[1]