华师一附中OI组

标题: P4302 [SCOI2003]字符串折叠 [打印本页]

作者: admin 时间: 2018-5-17 13:36
标题: P4302 [SCOI2003]字符串折叠
https://www.luogu.org/problemnew/show/P4302

题目描述
折叠的定义如下：

一个字符串可以看成它自身的折叠。记作S = S
X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB

给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

输入输出格式
输入格式：
仅一行，即字符串S，长度保证不超过100。

输出格式：
仅一行，即最短的折叠长度。

输入输出样例
输入样例#1：
NEERCYESYESYESNEERCYESYESYES
输出样例#1：
14
说明
一个最短的折叠为：2(NEERC3(YES))

欢迎光临华师一附中OI组 (http://hsyit.cn/)