419
правок
Изменения
Нет описания правки
== Базовые определения ==
{{Определение
|definition =
'''Конкатенацией''' строк <tex>\alpha = \sum^k</tex> и <tex>\beta = \sum^m</tex> является строка <tex>\alpha\beta = \sum^{k+m}</tex>. Конкатенация является ассоциативной операцией.
}}
{{Определение
|definition =
'''Нейтральным элементом''' <tex>\epsilon varepsilon \in \sum^{0}</tex> называется элемент, для которого верно <tex>\alpha\epsilonvarepsilon=\epsilon\alpha=\alpha</tex>.
}}
== Отношения между строками ==
{{Определение
<tex>\alpha</tex> называется '''префиксом''' <tex>\beta</tex>, если <tex>\beta = \alpha \gamma</tex>. Аналогично определяется '''суффикс''' строки.
}}
Пусть <tex>\beta = abracadabra</tex>, тогда
*если <tex>\alpha = abrac</tex>, то <tex>\alpha</tex> является префиксом <tex>\beta</tex>
*если <tex>\alpha = adabra</tex>, то суффиксом.
{{Определение
<tex>\alpha</tex> называется '''бордером''' <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и суффиксом и префиксом.
}}
Пусть <tex>\beta = abracadabra</tex>, тогда <tex>\alpha = abra</tex> будет бордером <tex>\beta</tex>.
{{Определение
Строка <tex>\alpha</tex> называется '''периодической''', если <tex>\alpha = \beta^k</tex>, для некоторого <tex>k > 1</tex>.
}}
{{Определение
|definition =
<tex>r</tex> называется '''периодом''' <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots n - r</tex> <tex>\alpha [i] = \alpha[i + r]</tex>. Если <tex>n = kr</tex>, где <tex>k > 1</tex>, то строка называется '''сильнопериодической'''.
}}
Строка <tex>\alpha = abraabraabra</tex> является сильнопериодической (<tex>\beta = abra, k = 3, r = 4</tex>).
{{Определение
|definition =
Строка <tex>\alpha</tex> является '''подстрокой''' <tex>\beta</tex>, если <tex>\beta = \gamma \alpha \delta</tex>.
}}
Строка <tex>\alpha = aca</tex> является подстрокой <tex>\beta = abracadabra</tex>.
{{Определение
|definition =
* <tex>\alpha</tex> префикс <tex>\beta</tex>
* <tex>\gamma</tex> общий префикс <tex>\alpha</tex> и <tex>\beta</tex>, <tex>\alpha = \gamma c \delta</tex>, <tex>\beta = \gamma d \xi</tex> и <tex>c < d</tex>
}}
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
