Jump to content

Подстрока

(Перенаправлено из Подстроки )
" строка " является подстрокой " подстроки "

В теории формального языка и информатике подстрока представляет собой непрерывную последовательность символов внутри строки . [ нужна ссылка ] Например, « лучшее из » является подстрокой « Это были лучшие времена ». Напротив, « 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

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

Граница — это суффикс и префикс одной и той же строки, например «баб» — это граница слова «бабаб» (а также «бабуин, поедающий шашлык»). [ нужна ссылка ]

Суперструна

[ редактировать ]

Суперструна множества конечного строк — это одна строка, содержащая каждую строку в как подстрока. Например, представляет собой суперстроку , и является более коротким. Объединение всех членов в произвольном порядке всегда получает тривиальную суперстроку . Найти суперструны минимально возможной длины — более интересная задача.

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

См. также

[ редактировать ]
  1. ^ Jump up to: а б с Лотер, М. (1997). Комбинаторика слов . Кембридж: Издательство Кембриджского университета. ISBN  0-521-59924-5 .
  2. ^ Келли, Дин (1995). Автоматы и формальные языки: Введение . Лондон: Prentice-Hall International. ISBN  0-13-497777-7 .
  3. ^ Гасфилд, Дэн (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . США: Издательство Кембриджского университета. ISBN  0-521-58519-8 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a1071a3027bb585af3d0cf063645699c__1703106240
URL1:https://arc.ask3.ru/arc/aa/a1/9c/a1071a3027bb585af3d0cf063645699c.html
Заголовок, (Title) документа по адресу, URL1:
Substring - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)