Изменения

Перейти к: навигация, поиск

Участник:Shersh/temporary

5570 байт убрано, 23:48, 12 июня 2014
что осталось
{{Определение
|definition='''Символ''' (англ. ''symbol'') {{---}} объект, имеющий собственное содержание и уникальную читаемую форму.}} {{Определение|definition='''Алфавит''' (англ. ''alphabet'') <tex>\Sigma</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='''Цепочка''' (англ. ''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>.
}}
}}
==Отношения между строками==
 
{{Определение
|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.
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/38935»

Навигация