P8131 [ICPC 2020 WF] Gene Folding

ICPC2020 WF D

国际细胞加工公司(ICPC)在基因序列分析方面处于世界领先地位。遗传序列是核苷酸的序列，在这个问题中，它由一个只包含字母 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$ 和 $\texttt{T}$ 的某种组合的字符串来表示，每个字母分别代表一个核苷酸腺嘌呤（$\textbf{A}$denine）、胞嘧啶（$\textbf{C}$ytosine）、鸟嘌呤（$\textbf{G}$uanine）和胸腺嘧啶（$\textbf{T}$hymine）。 ICPC 的一个重要发现是，通过一种被称为基因优化有机折叠（GOOF）的过程，他们可以将一个基因序列转化为一个更简单的序列，同时保留ICPC想要分析的序列的许多属性。 以下是 GOOF 的一个应用。在核苷酸序列中两个相邻核苷酸之间找到一个点，使从该点开始的序列在两个方向上都是相同的，直到序列的最后一个点。例如，在序列 $\texttt{ATTACC}$ 中，有两个这样的点：$\texttt{AT-TACC}$ 和 $\texttt{ATTAC-C}$。然后选择其中一个点(比如第一个点)，在那个点折叠基因序列，合并相同的核苷酸（因此，在这种情况下，$\texttt{AT}$ 和 $\texttt{TA}$ 会合并，得到的序列将是 $\texttt{CCAT}$ 或 $\texttt{TACC}$）。 通过重复使用 GOOF，可以使核苷酸变得更短。但是，手工寻找合适的折叠点非常耗时。ICPC 找到你，让你写一个程序来自动找到折叠点并选择它们，从而从给定的输入序列中获得尽可能短的基因序列。

输入包含一个表示要分析的核苷酸序列的字符串。只包含 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$ 和 $\texttt{T}$。$s$ 长度在 $1 \sim 4\cdot10^6$ 之间。

输出从输入中应用零次或多次 GOOF 得到的序列的最小可能长度。