bzoj#P4044. [Cerc2014] Virus synthesis

[Cerc2014] Virus synthesis

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC
3
8
6
18

数据范围

对于 100%100\% 的数据,S105|S|\le 10^5