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

Материал из Викиконспекты
Версия от 12:41, 23 июня 2013; Megabyte (обсуждение | вклад) (Отношения между строками)
Перейти к: навигация, поиск

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

Определение:
Алфавитом [math]\Sigma[/math] называется конечное непустое множество элементов, называемых символами.


Определение:
Нейтральный элемент (пустую строку) обозначим как [math]\varepsilon \in \Sigma^{0}[/math]. Для любой строки [math]\alpha[/math] верно: [math]\alpha\varepsilon=\varepsilon\alpha=\alpha[/math].


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


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


[math]\Sigma^*[/math] с операцией конкатенации и нейтральным элементом [math]\varepsilon[/math] образуют моноид. Данный моноид совпадает со свободным над [math]\Sigma[/math].

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

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


Пусть [math]\beta = \underline{abr}acada\underline{bra}[/math], тогда

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


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


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


Определение:
Число [math]p[/math] называется периодом строки [math]\alpha[/math] ([math]n = |\alpha|[/math]), если [math]\forall i = 1 \ldots n - p[/math] [math]\alpha [i] = \alpha[i + p][/math].


Строка [math]\alpha = acaacaa[/math] является периодической ([math]p = 3[/math]).


Определение:
Строка [math]\alpha \neq \varepsilon[/math], имеющая период [math]p[/math] ([math]p \neq |\alpha|[/math]), называется сильнопериодической с периодом [math]p[/math], если [math]|\alpha| \bmod p = 0[/math].


Строка [math]\alpha = acaacaaca[/math] является сильнопериодической ([math]p = 3[/math]).


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


Строка [math]\alpha = aca[/math] является подстрокой [math]\beta = abr\underline{aca}dabra[/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]


Строка [math]\alpha = aca \le \beta = acaaba[/math], т.к. является префиксом [math]\beta[/math].

Строка [math]\alpha = acaa \le \beta = acab[/math], т.к. [math]a \le b[/math].

Литература

  • Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.