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$ ~ $4\cdot10^6$之间。

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