#P4044. [Cerc2014] Virus synthesis

    ID: 3246 传统题 3000ms 128MiB 尝试: 533 已通过: 139 难度: 8 上传者: 标签>CF2500提高+/省选-回文树DAG 动态规划回文后缀链接倍增跳转消除被支配候选

[Cerc2014] Virus synthesis

题目描述

你要用 ATGC 四个字母用两种操作拼出给定的串:

1.将其中一个字符放在已有串开头或者结尾。

2.将已有串复制,然后翻转,再接在已有串的头部或者尾部。

一开始已有串为空。求最少操作次数。

输入格式

第一行一个整数 TT,表示有 TT 组数据。

接下来 TT 行每行一个字符串 SS。

输出格式

对于每组数据输出一行一个答案,即最少操作次数。

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC
3
8
6
18

数据范围

对于 100%100\% 的数据,∣S∣≤105|S|\le 10^5。