2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Строки без повторяющихся подстрок
Сообщение20.12.2016, 08:56 
Заслуженный участник


08/04/08
8504
Придумал легкую задачу, возможно она подойдет для школьников. Постю только потому, что хочу узнать, баян или нет.

Пусть $x$ - строка в каком-то конечном алфавите.
Назовем строку $x$ сложной, если в ней есть несколько вхождений одинаковых неперекрывающихся подстрок длины $>1$ (например, подстрока $ab$ в $ababa$), иначе назовем строку $x$ простой.
Какова максимальная длина простой строки в алфавите из $k$ символов?

 Профиль  
                  
 
 Re: Строки без повторяющихся подстрок
Сообщение20.12.2016, 13:50 
Аватара пользователя


29/04/13
3668
Богородский
Sonic86 в сообщении #1178533 писал(а):
Какова максимальная длина простой строки в алфавите из $k$ символов?

$k^2+k+1$

Например, вариант максимальной строки для $k=4$:

$aaabbbcccdddacbdbadca$

 Профиль  
                  
 
 Re: Строки без повторяющихся подстрок
Сообщение22.12.2016, 11:20 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Sonic86 в сообщении #1178533 писал(а):
Какова максимальная длина простой строки в алфавите из $k$ символов?

Рассмотрим произвольную простую строку. Пусть первая и последняя буквы разные, тогда каждая из $k$ букв входит в эту строку не более чем $k+1$ раз, то есть длина такой строки не превышает $k^2+k.$ Если же первая и последняя буквы совпадают, то эта буква входит в строку не более чем $k+2$ раза, а остальные не более чем $k+1$ раз, то есть длина такой строки не превышает $k^2+k+1.$ Из чего следует, что $$l_k \leqslant k^2+k+1$$Возьмём простую строку $\alpha$ в алфавите $A$ из $k$ букв максимальной длины. Пусть буква $z$ не входит в алфавит, а слово заканчивается, например, буквой $a.$ Тогда можно построить простое слово в алфавите $A\cup \{z\}$ из $k+1$ букв длиной $l_k+2(k+1),$ например$$\alpha zzzbzczd\dots za$$ То есть $l_k+2(k+1)\leqslant l_{k+1}.$ А так как $l_1=3,$ то $$k^2+k+1\leqslant l_k$$ Следовательно $$l_k=k^2+k+1$$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group