loj#P6793. 「ICPC World Finals 2020」基因折叠

「ICPC World Finals 2020」基因折叠

题目描述

国际细胞处理公司(ICPC)是一个世界领先的基因序列分析机构。基因序列是一段核苷酸序列,在本题中用一个仅由 A, G, C, T\texttt{A, G, C, T} 四个字母组成的字符串来表示,其中每个字母代表一个核苷酸分子(分别是腺嘌呤脱氧核苷酸 (Adenine),胞嘧啶脱氧核苷酸 (Cytosine),鸟嘌呤脱氧核苷酸 (Guanine),胸腺嘧啶脱氧核苷酸 (Thymine))。

ICPC 的重要发现之一是,通过一种叫做基因优化有机折叠(Genetically Optimized Organic Folding, GOOF)的操作,可以在保留基因序列中 ICPC 想要研究的许多特征的同时,将原基因序列转变为一个更简单的基因序列。

一个简单的 GOOF 操作如下所示。找到核苷酸序列中两个相邻核苷酸之间的一点,满足从这个点开始,向两边读取,一直取到离该点较近的字符串的一段,读取到的字符串相同。例如,在序列 ATTACC\texttt{ATTACC} 中,有两个这样的点:AT-TACC\texttt{AT-TACC}ATTAC-C\texttt{ATTAC-C}。然后选择其中一个点(比如第一个),然后沿这个点将这段基因序列折叠起来,合并相同的核苷酸(因此,在这个例子中 AT\texttt{AT}TA\texttt{TA} 会合并起来,得到的序列可能是 CCAT\texttt{CCAT}TACC\texttt{TACC})。

通过重复 GOOF 操作,一段核苷酸序列可以变得十分短。然而,手工找到恰当的折叠点十分耗时。ICPC 想让你写个程序自动化这个找折叠点的过程,输入一个核苷酸序列,找到经过折叠操作后能得到的最短核苷酸序列。

输入格式

输入包含一个字符串 ss,表示要分析的核苷酸序列。这个字符串仅由 A, G, C, T\texttt{A, G, C, T} 四个字母组成。ss 的长度在 1141064\cdot 10^6 之间(包括两端)。

输出格式

输出经过零次或更多次 GOOF 操作后能得到的最短核苷酸序列的长度。

ATTACC

3

AAAAGAATTAA

5