CF391B.Word Folding

You will receive 5 points for solving this problem.

Manao has invented a new operation on strings that is called folding. Each fold happens between a pair of consecutive letters and places the second part of the string above first part, running in the opposite direction and aligned to the position of the fold. Using this operation, Manao converts the string into a structure that has one more level than there were fold operations performed. See the following examples for clarity.

We will denote the positions of folds with '|' characters. For example, the word "ABRACADABRA" written as "AB|RACA|DAB|RA" indicates that it has been folded three times: first, between the leftmost pair of 'B' and 'R' letters; second, between 'A' and 'D'; and third, between the rightmost pair of 'B' and 'R' letters. Here are several examples of folded strings:

"ABCDEF|GHIJK" | "A|BCDEFGHIJK" | "AB|RACA|DAB|RA" | "X|XXXXX|X|X|XXXXXX"
| | | XXXXXX
KJIHG | KJIHGFEDCB | AR | X
ABCDEF | A | DAB | X
| | ACAR | XXXXX
| | AB | X

One last example for "ABCD|EFGH|IJ|K":

K
IJ
HGFE
ABCD

Manao noticed that each folded string can be viewed as several piles of letters. For instance, in the previous example, there are four piles, which can be read as "AHI", "BGJK", "CF", and "DE" from bottom to top. Manao wonders what is the highest pile of identical letters he can build using fold operations on a given word. Note that the pile should not contain gaps and should start at the bottom level. For example, in the rightmost of the four examples above, none of the piles would be considered valid since each of them has gaps, starts above the bottom level, or both.

解决本题可获得 5 分。

马瑙（Manao）发明了一种作用于字符串的新操作，称为“折叠”（folding）。每次折叠均发生在一对相邻字母之间，将字符串的后半部分置于前半部分之上，且后半部分反向书写，并与折叠位置对齐。通过该操作，马瑙将字符串转换为一种结构，其层级数比执行的折叠操作次数多一。以下示例可帮助理解。

我们将折叠位置用字符 | 表示。例如，单词 "ABRACADABRA" 写作 "AB|RACA|DAB|RA"，表示共进行了三次折叠：第一次在最左侧的 'B' 和 'R' 之间；第二次在 'A' 和 'D' 之间；第三次在最右侧的 'B' 和 'R' 之间。以下是若干折叠字符串的示例：

"ABCDEF|GHIJK" | "A|BCDEFGHIJK" | "AB|RACA|DAB|RA" | "X|XXXXX|X|X|XXXXXX"
| | | XXXXXX
KJIHG | KJIHGFEDCB | AR | X
ABCDEF | A | DAB | X
| | ACAR | XXXXX
| | AB | X

最后一个示例 "ABCD|EFGH|IJ|K" 的折叠结果如下：

K
IJ
HGFE
ABCD

马瑙注意到，每个折叠后的字符串均可视为若干列（pile）字母。例如，在上一个例子中，共有四列，若自底向上阅读，则各列为 "AHI"、"BGJK"、"CF" 和 "DE"。马瑙想知道：对给定单词进行折叠操作后，所能构造出的最高的一列完全相同的字母是多少？注意：该列中不能存在空缺（gap），且必须从最底层开始。例如，在上述四个示例中最右侧的那个中，没有任何一列是有效的，因为每列都存在空缺、未从最底层开始，或二者兼有。

The input will consist of one line containing a single string of n characters with 1 ≤ n ≤ 1000 and no spaces. All characters of the string will be uppercase letters.

This problem doesn't have subproblems. You will get 5 points for the correct submission.

输入包含一行，该行是一个长度为 $n$ 的字符串，其中 $1 \leq n \leq 1000$，且字符串中不含空格。字符串中的所有字符均为大写字母。

本题没有子问题。正确提交可获得 5 分。

Print a single integer — the size of the largest pile composed of identical characters that can be seen in a valid result of folding operations on the given string.

输出一个整数——在对给定字符串执行有效的折叠操作后，所能得到的、由相同字符组成的最大堆叠的大小。

Consider the first example. Manao can create a pile of three 'A's using the folding "AB|RACAD|ABRA", which results in the following structure:

ABRA
DACAR
AB

In the second example, Manao can create a pile of three 'B's using the following folding: "AB|BB|CBDB".

CBDB
BB
AB

Another way for Manao to create a pile of three 'B's with "ABBBCBDB" is the following folding: "AB|B|BCBDB".

BCBDB
B
AB

In the third example, there are no folds performed and the string is just written in one line.

考虑第一个例子。Manao 可以通过折叠方式 "AB|RACAD|ABRA" 构造出一叠三个 'A'，结果结构如下：

ABRA
DACAR
AB

在第二个例子中，Manao 可以通过以下折叠方式 "AB|BB|CBDB" 构造出一叠三个 'B'：

CBDB
BB
AB

另一种用 "ABBBCBDB" 构造三个 'B' 的折叠方式是 "AB|B|BCBDB"：

BCBDB
B
AB

在第三个例子中，未执行任何折叠操作，字符串仅写成一行。