P14021 [ICPC 2024 Nanjing R] 博德之跃 2

由于评测机性能差异，本题时限相较原题提升了 1 秒。

您有一个由小写英文字母组成的字符串 $S$。您需要对 $S$ 执行若干次操作，直到它变为空字符串。每次您可以执行以下三种操作中的一种： - 删除 $S$ 的第一个字符。 - 删除 $S$ 的最后一个字符。 - 选择 $S$ 的一个好子串 $S'$，并将 $S$ 替换为 $S'$。 一个非空字符串 $S'$ 被称为 $S$ 的好子串，当且仅当 $S'\neq S$，$S'$ 是 $S$ 的前缀，且 $S'$ 的反串是 $S$ 的后缀。长度为 $k$ 的字符串 $p_1p_2\cdots p_k$ 的反串是另一个长度为 $k$ 的字符串 $p_kp_{k-1}\cdots p_1$。 求最多能执行多少次第 $3$ 种操作。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据： 第一行输入一个由小写字母组成的字符串 $S$（$1\le |S|\le 10^5$）。 保证所有测试数据 $|S|$ 之和不超过 $2\times 10^5$。

每组测试数据输出一行一个整数，表示最多能执行多少次第 $3$ 种操作。

对于第一组样例数据：$\texttt{aaaa} \xrightarrow{\text{op. 3}} \texttt{aaa} \xrightarrow{\text{op. 3}} \texttt{aa} \xrightarrow{\text{op. 3}} \texttt{a} \xrightarrow{\text{op. 2}} \varnothing$。 对于第二组样例数据：$\texttt{abbaabba} \xrightarrow{\text{op. 3}} \texttt{abbaabb} \xrightarrow{\text{op. 1}} \texttt{bbaabb} \xrightarrow{\text{op. 3}} \texttt{bbaab} \xrightarrow{\text{op. 1}} \texttt{baab} \xrightarrow{\text{op. 3}} \texttt{baa} \xrightarrow{\text{op. 1}} \texttt{aa} \xrightarrow{\text{op. 3}} \texttt{a} \xrightarrow{\text{op. 1}} \varnothing$。