Основные определения, связанные со строками

Базовые определения

Определение:

Алфавитом [math]\sum[/math] называется конечное непустое множество символов.

Определение:

Цепочкой (словом, строкой) конечной длины обозначим [math]\sum^* : \sum^* = \bigcup\limits_{n \in \mathbb N} \sum^n[/math].

Определение:

Конкатенацией строк [math]\alpha = \sum^k[/math] и [math]\beta = \sum^m[/math] является строка [math]\alpha\beta = \sum^{k+m}[/math]. Конкатенация является ассоциативной операцией.

Определение:

Нейтральным элементом [math]\varepsilon \in \sum^{0}[/math] называется элемент, для которого верно [math]\alpha\varepsilon=\epsilon\alpha=\alpha[/math].

Отношения между строками

Определение:

[math]\alpha[/math] называется префиксом [math]\beta[/math], если [math]\beta = \alpha \gamma[/math]. Аналогично определяется суффикс строки.

Пусть [math]\beta = abracadabra[/math], тогда

• если [math]\alpha = abrac[/math], то [math]\alpha[/math] является префиксом [math]\beta[/math]
• если [math]\alpha = adabra[/math], то суффиксом.

Определение:

[math]\alpha[/math] называется бордером [math]\beta[/math], если [math]\alpha[/math] одновременно является и суффиксом и префиксом.

Пусть [math]\beta = abracadabra[/math], тогда [math]\alpha = abra[/math] будет бордером [math]\beta[/math].

Определение:

Строка [math]\alpha[/math] называется периодической, если [math]\alpha = \beta^k[/math], для некоторого [math]k \gt 1[/math].

Определение:

[math]r[/math] называется периодом [math]\alpha[/math], если [math]\forall i = 1 \ldots n - r[/math] [math]\alpha [i] = \alpha[i + r][/math]. Если [math]n = kr[/math], где [math]k \gt 1[/math], то строка называется сильнопериодической.

Строка [math]\alpha = abraabraabra[/math] является сильнопериодической ([math]\beta = abra, k = 3, r = 4[/math]).

Определение:

Строка [math]\alpha[/math] является подстрокой [math]\beta[/math], если [math]\beta = \gamma \alpha \delta[/math].

Строка [math]\alpha = aca[/math] является подстрокой [math]\beta = abracadabra[/math].

Определение:

Строка [math]\alpha \le \beta[/math], если: [math]\alpha[/math] префикс [math]\beta[/math] [math]\gamma[/math] общий префикс [math]\alpha[/math] и [math]\beta[/math], [math]\alpha = \gamma c \delta[/math], [math]\beta = \gamma d \xi[/math] и [math]c \lt d[/math]