#C. [SCOI2003] 字符串折叠

    Type: RemoteJudge 1000ms 125MiB

[SCOI2003] 字符串折叠

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

折叠的定义如下:

  1. 一个字符串可以看成它自身的折叠。记作 S = S

  2. X(S)XXS 连接在一起的串的折叠。记作 X(S) = SSSS…S

  3. 如果 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,长度保证不超过 100100

输出格式

仅一行,即最短的折叠长度。

NEERCYESYESYESNEERCYESYESYES
14

提示

一个最短的折叠为:2(NEERC3(YES))

9月8日居家练习

Not Attended
Status
Done
Rule
IOI
Problem
4
Start at
2023-9-8 9:00
End at
2023-9-8 13:00
Duration
4 hour(s)
Host
Partic.
17