Подстрока

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

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

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

Подстроки строки « яблоко » будут такими: « а », « ап », « приложение », « приложение », « яблоко », « п », « пп », « пппл », « пппл », " пл ", " пле ", « л », « ле » " е ", "" (обратите внимание на пустую строку в конце).

Подстрока

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

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

banana
 |||||
 ana||
   |||
   ana

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

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

Префикс

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

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

banana
|||
ban

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

Суффикс

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

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

banana
  ||||
  nana

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

Граница

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

Суперструна

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

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

См. также

Ссылки

^ 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 .

[Lot97-1] Jump up to: ^а ^б ^с Лотер, М. (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]