{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e在看起来很随机的字符串中找规律是一个有许多应用的问题。比如说,在研究基因组的过程中我们需要观察 DNA 序列的结构。在数据压缩中我们可能需要寻找重复的部分,这样数据就可以用指针来更高效地存储。另一个例子是在 AI 研究中产生的,关于如何解读一段用你不懂的语言描述的信息。一个很自然的想法就是寻找这段信息当中的重复内容。所以如果 SETI 在 H21 光谱中捕获了一个信号,我们需要知道如何解读它。\u003c/p\u003e\n\n\u003cp\u003e一个发现字符串冗余的方法是寻找它的分解。如果两个或多个相同的字符串 $A$ 在字符串 $S$ 中连续出现,那么我们可以用 $(A)^p$ 来表示这段子串,其中 $p$ 表示 $A$ 重复的次数。比如说,字符串 $DOODOO$ 可以被分解成 $(DOO)^2$,还可以被进一步分解成 $(D(O)^2)^2$。我们认为第二种分解是更优的,因为它没法被进一步分解。如果一个分解不再包含连续出现的相同子串,我们就称它是最简的。一个字符串可能有多种最简的分解,比如 $POPPOP$。它可以被分解成 $(POP)^2$,也可以是 $PO(P)^2OP$。第一种分解更短,所以可以引入如下的定义:我们把分解的权值定义为它除了括号和指数之外的部分的长度,比如 $PO(P)^2OP$ 的权值是 $5$。最大分解是拥有最小权值的分解。显然一个最大分解一定是最简的,但是一个字符串仍然可能有多个最大分解。比如字符串 $ABABA$ 有两个最大分解 $(AB)^2A$ 和 $A(BA)^2$,他们的权值都是 $3$。\u003c/p\u003e"}},{"title":"输入","value":{"format":"MD","content":"输入包含若干行。每一行是一个长度在 $[1,79]$ 范围内的字符串,这个字符串由大写字母组成。输入的结束由一个只有一个星号 $*$ 的行来标志。输入中没有空白字符。"}},{"title":"输出","value":{"format":"MD","content":"对于输入的每个字符串,输出一行:它最大分解的权值。"}},{"title":"样例输入","value":{"format":"MD","content":"```plaintext\nPRATTATTATTIC\nGGGGGGGGG\nPRIME\nBABBABABBABBA\nARPARPARPARPAR\n*\n```"}},{"title":"样例输出","value":{"format":"MD","content":"```plaintext\n6\n1\n5\n6\n5\n```"}}]}