Codeforces Round 853 (Div. 2) |
---|
Закончено |
Serval любит Brain Power и свою интеллектуальную задачу.
Serval называет строку $$$T$$$ мощной тогда и только тогда, когда $$$T$$$ можно получить конкатенацией некоторой строки $$$T'$$$ несколько раз. Формально говоря, $$$T$$$ является мощной тогда и только тогда, когда существует строка $$$T'$$$ и целое число $$$k\geq 2$$$ такие, что $$$$$$T=\underbrace{T'+T'+\dots+T'}_{k\text{ раз}}$$$$$$
Например, gogogo является мощной, потому что её можно получить конкатенацией go три раза, но power не является мощной.
У Serval есть строка $$$S$$$, состоящая из строчных латинских букв. Ему любопытно узнать о самой длинной мощной подпоследовательности $$$S$$$, и ему достаточно, чтобы вы узнали её длину. Если все непустые подпоследовательности $$$S$$$ не являются мощными, ответ считается равным $$$0$$$.
Строка $$$a$$$ является подпоследовательностью строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов.
Первая строка содержит единственную строку $$$S$$$ ($$$|S|\leq 80$$$), состоящую из строчных латинских букв.
Выведите единственное целое число — длину самой длинной мощной подпоследовательности $$$S$$$. Если все непустые подпоследовательности $$$S$$$ не являются мощными, выведите $$$0$$$.
buaa
2
codeforcesround
6
oooooooooooaaaaeaaiaujooooooooooooo
24
zero
0
В первом примере все непустые подпоследовательности buaa перечислены ниже:
Так как aa $$$=$$$ a $$$+$$$ a, aa является мощной подпоследовательностью. Можно доказать, что aa является единственной мощной подпоследовательностью среди них. Поэтому ответ равен $$$2$$$.
Во втором примере самой длинной мощной подпоследовательностью является codcod из codeforcesround. Поэтому ответ равен $$$6$$$.
Название |
---|