loj#P6793. 「ICPC World Finals 2020」基因折叠
「ICPC World Finals 2020」基因折叠
题目描述
国际细胞处理公司(ICPC)是一个世界领先的基因序列分析机构。基因序列是一段核苷酸序列,在本题中用一个仅由 四个字母组成的字符串来表示,其中每个字母代表一个核苷酸分子(分别是腺嘌呤脱氧核苷酸 (Adenine),胞嘧啶脱氧核苷酸 (Cytosine),鸟嘌呤脱氧核苷酸 (Guanine),胸腺嘧啶脱氧核苷酸 (Thymine))。
ICPC 的重要发现之一是,通过一种叫做基因优化有机折叠(Genetically Optimized Organic Folding, GOOF)的操作,可以在保留基因序列中 ICPC 想要研究的许多特征的同时,将原基因序列转变为一个更简单的基因序列。
一个简单的 GOOF 操作如下所示。找到核苷酸序列中两个相邻核苷酸之间的一点,满足从这个点开始,向两边读取,一直取到离该点较近的字符串的一段,读取到的字符串相同。例如,在序列 中,有两个这样的点: 和 。然后选择其中一个点(比如第一个),然后沿这个点将这段基因序列折叠起来,合并相同的核苷酸(因此,在这个例子中 和 会合并起来,得到的序列可能是 或 )。
通过重复 GOOF 操作,一段核苷酸序列可以变得十分短。然而,手工找到恰当的折叠点十分耗时。ICPC 想让你写个程序自动化这个找折叠点的过程,输入一个核苷酸序列,找到经过折叠操作后能得到的最短核苷酸序列。
输入格式
输入包含一个字符串 ,表示要分析的核苷酸序列。这个字符串仅由 四个字母组成。 的长度在 到 之间(包括两端)。
输出格式
输出经过零次或更多次 GOOF 操作后能得到的最短核苷酸序列的长度。
ATTACC
3
AAAAGAATTAA
5