1294
правки
KEV (обсуждение | вклад) (Создана новая страница размером {Цепочка}{String, word} {последовательность символов некоторого алфавита <math>\Sigma</...) |
KVN (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
'''Цепочка'''([[string]], [[word]]) --- последовательность символов некоторого алфавита <math>\Sigma</math>, | |||
расположенных один за другим. | расположенных один за другим. | ||
''Длина'' цепочки --- число символов в ней. Цепочка нулевой | [[Длина цепочки |''Длина'' цепочки]] --- число символов в ней. Цепочка нулевой | ||
длины называется ''пустой''. | длины называется [[Пустая цепочка|''пустой'']]. | ||
Цепочка <math>z=xy</math> называется ''конкатенацией'' (или | Цепочка <math>z=xy</math> называется [[конкатенация|''конкатенацией'']] (или [[сцепление|''сцеплением'']]) цепочек <math>x</math> и <math>y</math>. ''Обращением'' цепочки <math>x</math> | ||
сцеплением | |||
называется цепочка <math>x</math>, записанная в обратном порядке. Цепочка | называется цепочка <math>x</math>, записанная в обратном порядке. Цепочка | ||
<math>a^k</math>, называемая <math>k</math>-''кратной конкатенацией'' некоторого | <math>a^k</math>, называемая <math>k</math>-''кратной конкатенацией'' некоторого | ||
Строка 13: | Строка 11: | ||
<math>a^k=a a^{k-1}</math> для любого <math>k>0</math>. | <math>a^k=a a^{k-1}</math> для любого <math>k>0</math>. | ||
Цепочка <math>x</math> называется ''префиксом'', | Цепочка <math>x</math> называется [[префикс|''префиксом'']], | ||
а цепочка <math>y</math> --- ''суффиксом'' | а цепочка <math>y</math> --- [[суффикс|''суффиксом'']] | ||
цепочки <math>w=xy</math>. Цепочка <math>z</math> --- ''подцепочка'' цепочки <math>s= xzy</math>. | цепочки <math>w=xy</math>. Цепочка <math>z</math> --- [[подцепочка|''подцепочка'']] цепочки <math>s= xzy</math>. | ||
Другие названия --- [[Слово|''Слово'']],[[Строка|''Строка'']]. | |||
==Литература== | ==Литература== | ||
[Ахо-Ульман], | [Ахо-Ульман], | ||
Строка 25: | Строка 22: | ||
[Касьянов-Поттосин], | [Касьянов-Поттосин], | ||
[Касьянов/95] | [Касьянов/95] | ||
[Евстигнеев-Касьянов/94] | [Евстигнеев-Касьянов/94] |