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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Алфавитом [math]\sum[/math] называется конечное непустое множество символов.


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


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


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


Определение:
Строка [math]\alpha[/math] является подстрокой [math]\beta[/math], если [math]\beta = \gamma \alpha \delta[/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]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], то строка называется сильнопериодической.