P8368 [LNOI2022] String

To help you better understand the statement, here are some definitions about strings: - For a string $S = s_1 s_2 \cdots s_n$, its length is defined as $\lvert S \rvert = n$. - For two strings $S = s_1 s_2 \cdots s_n$ and $T = t_1 t_2 \cdots t_m$, we call $T$ a substring of $S$ if $m = 0$ (i.e., $T$ is the empty string) or $\exists 1 \le i \le j \le n$ such that $T = s_i s_{i + 1} \cdots s_j$. If $m = 0$ or in the above condition $i$ can be $1$, then $T$ is called a prefix of $S$; if $m = 0$ or in the above condition $j$ can be $n$, then $T$ is called a suffix of $S$. Given a string $S$ consisting of lowercase English letters, you need to find a string sequence $(T_0, T_1, \ldots, T_l)$ that is as long as possible, satisfying: - $T_0$ is a substring of $S$. - $\forall 1 \le i \le l$, $\lvert T_i \rvert - \lvert T_{i - 1} \rvert = 1$. - $\forall 1 \le i \le l$, there exists a substring $S'_i$ of $S$ with length $\lvert T_i \rvert + 1$, such that the prefix of $S'_i$ with length $\lvert T_{i - 1} \rvert$ is $T_{i - 1}$, and the suffix of $S'_i$ with length $\lvert T_i \rvert$ is $T_i$. Output the maximum possible length of such a sequence (i.e., the maximum value of $l$).

**This problem has multiple test cases**. The first line contains an integer $T$, denoting the number of test cases. For each test case, one line contains a string $S$ consisting of lowercase English letters.

For each test case, output one integer per line, representing the maximum length of the string sequence described in the statement.

**[Sample Explanation #1]** In the following, the symbol $\epsilon$ denotes the empty string. For the first test case, we can find the following string sequence: $T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{cd}$, where $S'_1 = \texttt{ab}, S'_2 = \texttt{bcd}$. For the second test case, we can find the following string sequence: $T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{ab}, T_3 = \texttt{bab}$, where $S'_1 = \texttt{ab}, S'_2 = \texttt{bab}, S'_3 = \texttt{abab}$. For the third test case, we can find the following string sequence: $T_0 = \epsilon$. **[Sample #2]** See the attachments `string/string2.in` and `string/string2.ans`. The string lengths in this sample have some gradients. You can use this sample to check your program. **[Sample #3]** See the attachments `string/string3.in` and `string/string3.ans`. This sample satisfies Special Property A. **[Constraints]** Let $\sum |S|$ denote the sum of string lengths of all test cases in a test. For $100 \%$ of the testdata, $T \ge 1$, $1 \le \lvert S \rvert \le 5 \times {10}^5$, $1 \le \sum \lvert S \rvert \le 1.5 \times {10}^6$. | Test Point ID | $\lvert S \rvert \le$ | $\sum \lvert S \rvert \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1 \sim 2$ | $30$ | $150$ | None | | $3 \sim 5$ | $200$ | $800$ | None | | $6 \sim 8$ | $1000$ | $3000$ | None | | $9 \sim 11$ | $5 \times {10}^5$ | $1.5 \times {10}^6$ | A | | $12 \sim 15$ | $6 \times {10}^4$ | $3 \times {10}^5$ | None | | $16 \sim 20$ | $5 \times {10}^5$ | $1.5 \times {10}^6$ | None | Special Property A: each character in the string is generated independently and uniformly at random among lowercase letters. **[Notes]** The input and output size of this problem is large, so please use faster I/O. For example, if your code uses `cin` and `cout` for I/O, you may add the following statements **after** the **I/O redirection statements** (`freopen`, `fopen`, etc.) to speed up I/O. ```cpp ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ``` **After adding these statements, it is not recommended to use `cin, cout` together with other I/O methods.** Translated by ChatGPT 5