419
правок
Изменения
Нет описания правки
}}
Пусть <tex>\beta = abracadabra\underline{abr}acada\underline{bra}</tex>, тогда*если <tex>\alpha = abracabr</tex>, то <tex>\alpha</tex> является префиксом <tex>\beta</tex>*если <tex>\alpha = adabrabra</tex>, то суффиксом.
{{Определение
}}
Пусть <tex>\beta = abracadabra\underline{abra}cad\underline{abra}</tex>, тогда <tex>\alpha = abra</tex> будет бордером <tex>\beta</tex>.
{{Определение
|definition =
<tex>p</tex> называется '''периодом''' <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots [n / p] * p - p\quad</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
|id=border
}}
Строка <tex>\alpha = acaacab</tex> является сильнопериодической (<tex>p = 3</tex>).
{{Определение
Строка <tex>\alpha</tex> называется сильнопериодической, если <tex>n</tex> <tex>mod</tex> <tex>p = 0</tex>.
}}
Строка <tex>\alpha = acaacaaca</tex> является сильнопериодической (<tex>p = 3</tex>).
{{Определение
}}
Строка <tex>\alpha = aca</tex> является подстрокой <tex>\beta = abracadabraabr\underline{aca}dabra</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>
}}
Строка <tex>\alpha = aca \le \beta = acaaba</tex>, т.к. является префиксом <tex>\beta</tex>.
Строка <tex>\alpha = acaa \le \beta = acab</tex>, т.к. <tex>a \le b</tex>.
==Литература==
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
