Изменения

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

Слово Туэ-Морса

422 байта добавлено, 14:11, 8 мая 2016
Свойство о подстроках
Не существует двух равных как строки подстрок строки <tex>T_n</tex>, имеющих пересекающиеся вхождения в <tex>T_n</tex>
|proof=
Очевидно Заметим, что <tex>t_{2n}=t_n</tex> для <tex>n \geqslant 0</tex>, так как количество единиц числа <tex>2n</tex> и <tex>n</tex> одинаково. Так же заметим, что <tex>t_{2n+1}=\varphi(t_n)</tex> для <tex>n \geqslant 0</tex>, потому что <tex>2n</tex> и <tex>2n+1</tex> одинаковы в двоичной системе, кроме последнего бита, а количество единиц числа <tex>2n</tex> и <tex>n</tex> одинаково
Пусть существует две равные как строки подстрок строки <tex>T_n</tex>, имеющих пересекающиеся вхождения в <tex>T_n</tex>, тогда <tex>T_n=ucxcxcv</tex>, где <tex>u,c,x,v</tex> {{---}} подстроки строки <tex>T_n</tex>, а строка <tex>cxc</tex> {{---}} искомая подстрока.

Навигация