|
|
| Строка 3: |
Строка 3: |
| | | | |
| | {{Определение | | {{Определение |
| − | |definition='''Символ''' (англ. ''symbol'') {{---}} объект, имеющий собственное содержание и уникальную читаемую форму.
| + | |definition='''Алфавит''' (англ. ''alphabet'') <tex>\Sigma</tex> {{---}} . |
| − | }}
| |
| − | | |
| − | {{Определение
| |
| − | |definition='''Алфавит''' (англ. ''alphabet'') <tex>\Sigma</tex> {{---}} непустое множество символов. | |
| | }} | | }} |
| | | | |
| | Примеры: | | Примеры: |
| | * <tex>\Sigma = \left\{0, 1\right\} </tex> {{---}} бинарный алфавит. | | * <tex>\Sigma = \left\{0, 1\right\} </tex> {{---}} бинарный алфавит. |
| − | * <tex>\Sigma = \left\{\cdot, -\right\} </tex> {{---}} алфавит, лежащий в основе азбуки Морзе.
| |
| − | * <tex>\Sigma = \left\{a, b, c, d, \dots, z\right\} </tex> {{---}} английский алфавит.
| |
| − | * <tex>\Sigma = \left\{0, 1, 2, \dots, 9\right\} </tex> {{---}} алфавит цифр.
| |
| − | * Нотные знаки
| |
| | | | |
| | {{Определение | | {{Определение |
| − | |definition='''Нейтральный элемент''' {{---}} пустая строка <tex>\varepsilon : \varepsilon \in \Sigma^{0}</tex>. Для любой строки <tex>\alpha \in \Sigma^k</tex> верно <tex> : \alpha\varepsilon=\varepsilon\alpha=\alpha</tex>. | + | |definition='''Нейтральный элемент''' {{---}} пустая строка <tex>\varepsilon : \varepsilon \in \Sigma^{0}</tex>. |
| | }} | | }} |
| | | | |
| Строка 29: |
Строка 21: |
| | {{Определение | | {{Определение |
| | |definition='''Цепочка''' (англ. ''chain'') {{---}} элемент конечной длины из <tex>\Sigma^*</tex>. | | |definition='''Цепочка''' (англ. ''chain'') {{---}} элемент конечной длины из <tex>\Sigma^*</tex>. |
| − | }}
| |
| − |
| |
| − | {{Определение
| |
| − | |definition='''Конкатенация''' (англ. ''concatenation'') {{---}} бинарная, ассоциативная, некоммутативная операция, определённая на словах данного алфавита. Конкатецния строк <tex>\alpha \in \Sigma^k</tex> и <tex>\beta \in \Sigma^m</tex> является строка <tex>\alpha\beta \in \Sigma^{k + m}</tex>.
| |
| | }} | | }} |
| | | | |
| Строка 39: |
Строка 27: |
| | }} | | }} |
| | | | |
| − | ==Отношения между строками==
| |
| − |
| |
| − | {{Определение
| |
| − | |id=prefix
| |
| − | |definition='''Префикс''' (англ. ''prefix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \beta = \alpha \gamma</tex>.
| |
| − | }}
| |
| − |
| |
| − | Пусть <tex>\beta = \underline{abr}acadabra</tex>, тогда <tex>\alpha = abr</tex> {{---}} префикс <tex>\beta</tex>.
| |
| − |
| |
| − | {{Определение
| |
| − | |id=suffix
| |
| − | |definition='''Суффикс''' (англ. ''suffix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \beta = \gamma \alpha </tex>.
| |
| − | }}
| |
| − |
| |
| − | Пусть <tex>\beta = abracada\underline{bra}</tex>, тогда <tex>\alpha = bra</tex> {{---}} суффикс <tex>\beta</tex>.
| |
| − |
| |
| − | {{Определение
| |
| − | |id=border
| |
| − | |definition='''Бордер''' (англ. ''circumfix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \beta = \gamma \alpha = \alpha \eta = \alpha \mu \alpha</tex>.
| |
| − | }}
| |
| − |
| |
| − | Пусть <tex>\beta = \underline{abra}cad\underline{abra}</tex>, тогда <tex>\alpha = abra</tex> {{---}} бордер <tex>\beta</tex>.
| |
| − |
| |
| − | {{Определение
| |
| − | |id=ind
| |
| − | |definition=<tex>\alpha[i]</tex> {{---}} обращение к символу под номером <tex>i</tex> строки <tex>\alpha</tex>.
| |
| − | }}
| |
| − |
| |
| − | Пусть <tex>\beta = cacao</tex>, тогда <tex>\beta[1] = c, \beta[4] = a </tex>.
| |
| − |
| |
| − | {{Определение
| |
| − | |id=period
| |
| − | |definition='''Период''' (англ. ''period'') строки <tex>\alpha</tex> {{---}} число <tex>p : \forall i = 1 \ldots |\alpha| - p,
| |
| − | \alpha [i] = \alpha[i + p]</tex>.
| |
| − | }}
| |
| − |
| |
| − | Пусть <tex>\alpha = acaacaa</tex>, тогда <tex>p = 3</tex> {{---}} период строки <tex>\alpha = acaacaa</tex>.
| |
| − |
| |
| − |
| |
| − | {{Утверждение
| |
| − | |statement=Пусть известна строка <tex>\tau</tex> {{---}} период <tex>\alpha</tex> и <tex>|\alpha|</tex>, тогда можно восстановить всю строку <tex>\alpha</tex>.
| |
| − | |proof=Из определения периода строки следует, что <tex>\alpha[1 \dots |\tau|] = \alpha[|\tau| + 1 \dots 2 \cdot |\tau|] = \dots = \alpha[|\tau| \cdot (k - 1) + 1 \dots |\tau| \cdot k] </tex>, где <tex>k = </tex> <tex dpi="140">\lfloor\frac{|\alpha|}{|\tau|} \rfloor</tex>.
| |
| − |
| |
| − | Таким образом <tex>\alpha = </tex><tex dpi="140">\sum \limits_{i=1}^{\lfloor\frac{|\alpha|}{|\tau|} \rfloor}</tex><tex> \tau + \tau[1 \dots |\alpha| \bmod |\tau|]</tex>.
| |
| − | }}
| |
| − |
| |
| − |
| |
| − | {{Определение
| |
| − | |id=hardperiod
| |
| − | |definition=Строка <tex>\alpha \neq \varepsilon</tex> c периодом <tex>p \neq |\alpha|</tex>, называется '''сильнопериодической''', если <tex>|\alpha| \bmod p = 0</tex>.
| |
| − | }}
| |
| − |
| |
| − | Строка <tex>\alpha = acaacaaca</tex> является сильнопериодической с периодом <tex>p = 3</tex>.
| |
| − |
| |
| − | {{Определение
| |
| − | |id=substring
| |
| − | |definition='''Подстрока''' (англ. ''substring'') {{---}} некоторая непустая подпоследовательность подряд идущих символов строки.
| |
| − | }}
| |
| − |
| |
| − | Пусть <tex>\beta = abr\underline{aca}dabra</tex>, тогда <tex>\alpha = aca</tex> {{---}} подстрока строки <tex>\beta</tex>.
| |
| − |
| |
| − | {{Определение
| |
| − | |definition =
| |
| − | Строка <tex>\alpha</tex> '''лексикографически меньше''' строки <tex>\beta</tex> (<tex>\alpha < \beta</tex>), если
| |
| − | 1. <tex>\alpha</tex> {{---}} префикс <tex>\beta</tex>
| |
| − |
| |
| − | ''или''
| |
| − |
| |
| − | 2. <tex> \mathcal {9} k : k \leqslant \min(|\alpha|, |\beta|) </tex> и <tex> \alpha[k] < \beta[k] </tex>, при этом <tex> \mathcal {8} j < k : \alpha_j = \beta_j </tex>
| |
| − | }}
| |
| − |
| |
| − | Строка <tex>\alpha = aca < \beta = acaaba</tex>, так как является префиксом <tex>\beta</tex>.
| |
| − |
| |
| − | Строка <tex>\alpha = acaa < \beta = acab</tex>, так как <tex>a < b</tex>.
| |
| − |
| |
| − | == Смотри также ==
| |
| − | [[Период и бордер, их связь]]
| |
| | | | |
| − | [[Слово Фибоначчи]]
| |
| | | | |
| − | [[Слово Туэ-Морса]]
| |
| | | | |
| | ==Литература== | | ==Литература== |
| − | * Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
| |
| − | * Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.
| |
| | * Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. | | * Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. |
| | | | |
| | [[Категория:Алгоритмы и структуры данных]] | | [[Категория:Алгоритмы и структуры данных]] |
| | [[Категория:Основные определения. Простые комбинаторные свойства слов]] | | [[Категория:Основные определения. Простые комбинаторные свойства слов]] |
