|
|
| Строка 50: |
Строка 50: |
| | {{Определение | | {{Определение |
| | |definition = | | |definition = |
| − | Пусть строка <tex>\alpha \in \Sigma^m</tex> имеет период <tex>p</tex>, <tex>r = m / p</tex> и <tex>\beta \in \Sigma^p</tex>. Тогда декомпозиция <tex>\alpha = \beta^r </tex> называется '''нормальной формой''' строковой последовательности <tex>\alpha</tex>.
| + | Строка <tex>\alpha</tex> называется сильнопериодической, если <tex>n</tex> <tex>mod</tex> <tex>p = 0</tex>. |
| | }} | | }} |
| − |
| |
| − | {{Определение
| |
| − | |definition =
| |
| − | Строка <tex>\alpha</tex> называется примитивной, если <tex>p = m -</tex> максимальный период (т.е. <tex>r = 1</tex>).
| |
| − | }}
| |
| − |
| |
| − | {{Определение
| |
| − | |definition =
| |
| − | Если <tex>r \ge 2</tex>, то строка <tex>\alpha</tex> называется '''сильнопериодической''', если <tex>1 < r < 2</tex>, то '''слабопериодической'''. Если <tex>r</tex> целое и <tex>r \ge 2</tex>, то строка <tex>\alpha</tex> называется '''строгопериодической''' (или просто '''периодической''').
| |
| − | }}
| |
| − |
| |
| − | Строка <tex>aaabaabab</tex> - примитивная <tex>(p = m)</tex>.
| |
| − |
| |
| − | Строка <tex>abaababaabaab = (abaababa)(abaab)</tex> - слабопериодическая с периодом <tex>p = 8</tex>, порядком <tex>r = 13/8</tex>.
| |
| − |
| |
| − | Строка <tex>abaabaab = (aba)^2(ab)</tex> - сильнопериодическая с периодом <tex>p = 3</tex>, порядком <tex>r = 8/3</tex>.
| |
| | | | |
| | {{Определение | | {{Определение |
Версия 17:58, 3 июня 2012
Базовые определения
| Определение: |
| Алфавитом [math]\Sigma[/math] называется конечное непустое множество элементов, называемых символами. |
| Определение: |
| Нейтральным элементом (пустой строкой) [math]\varepsilon \in \Sigma^{0}[/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 = 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]p[/math] называется периодом [math]\alpha[/math], если [math]\forall i = 1 \ldots n - p[/math] [math]\alpha [i] = \alpha[i + p][/math]. |
| Определение: |
| Строка [math]\alpha[/math] называется сильнопериодической, если [math]n[/math] [math]mod[/math] [math]p = 0[/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]
|
