Educational Codeforces Round 25 |
---|
Закончено |
Иван хочет написать письмо своему другу. Письмо — строка s, состоящая из строчных латинских букв.
К сожалению, как только Иван начал писать письмо, он понял, что оно слишком длинное, и писать его целиком придётся очень долго. Поэтому он хочет написать сжатую версию строки s вместо самой строки.
Сжатая версия строки s — последовательность строк c1, s1, c2, s2, ..., ck, sk, где ci — десятичная запись числа ai (без лидирующих нулей), а si — некоторая строка из строчных латинских букв. Если Иван запишет строку s1 ровно a1 раз, потом s2 ровно a2 раз, и так далее, у него получится строка s.
Длина сжатой версии равна |c1| + |s1| + |c2| + |s2|... |ck| + |sk|. Среди всех сжатых версий Иван хочет выбрать такую, что её длина минимальна. Помогите Ивану определить минимально возможную длину.
В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 8000).
Выведите одно целое число — минимальную длину сжатой версии строки s.
aaaaaaaaaa
3
abcab
6
cczabababab
7
В первом примере Иван выберет следующую версию: c1 — 10, s1 — a.
Во втором примере Иван выберет следующую версию: c1 — 1, s1 — abcab.
В третьем примере Иван выберет следующую версию: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.
Название |
---|