39
правок
Изменения
→Отношения между строками
{{Определение
|id=period
|definition='''Период''' (англ. ''Period'') строки <tex>\alpha</tex> {{---}} число <tex>p</tex>: <tex>\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...|\tau|] = \alpha[|\tau| + 1...2*|\tau|] = ... = \alpha[|\tau|*(k - 1) + 1...|\tau|*k] </tex>, где <tex>k = \lfloor\frac{|\alpha|}{|\tau|} \rfloor</tex>. Таким образом <tex>\alpha = \sum_{i=1}^{\lfloor\frac{|\alpha|}{|\tau|} \rfloor} \tau + \tau[1...|\alpha| mod |\tau|]</tex>.
}}
{{Определение
{{Определение
|definition =
Строка <tex>\alpha < \beta</tex>, если:* '''лексикографически меньше''' строки <tex>\alphabeta</tex> {{---}} префикс (<tex>\alpha < \beta</tex>), если* 1. <tex>\gammaalpha</tex> {{---}} общий префикс <tex>\alphabeta</tex> и ''или'' 2. <tex>\beta</tex>: <tex>mathcal {9} k\alpha = leqslant \gamma c min(|\delta</tex>alpha|, <tex>|\beta = |): \gamma d alpha[k] < \xibeta[k] </tex> и при этом <tex>c \mathcal {8} j < dk ~\alpha_j = \beta_j </tex>
}}
