#P4163. [2015年湖南省队省队集训]字符串合成

    ID: 3378 传统题 1000ms 512MiB 尝试: 135 已通过: 38 难度: 9 上传者: 标签>CF2600提高+/省选-回文树DAG 动态规划回文后缀链接倍增跳转

[2015年湖南省队省队集训]字符串合成

题目描述

给定四种对字符串 SS 的操作:

  1. push_back(P):在 SS 后连接一个字符串 PP,即 S=S+PS=S+P,代价为 ∣P∣|P|;
  2. push_front(P):在 SS 前连接一个字符串 PP,即 S=P+SS=P+S,代价为 ∣P∣|P|;
  3. symmetry_back():将 SS 翻转后连接在 SS 之后,即 S=S+rev⁡(S)S=S+\operatorname{rev}(S),代价为 11;
  4. symmetry_front():将 SS 翻转后连接在 SS 之前,即 S=rev⁡(S)+SS=\operatorname{rev}(S)+S,代价为 11;

给定一个目标串 SS,要求你通过上述四种操作,用最少的代价合成出目标串,初始只有一个空串。

输入格式

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

接下来 TT 行,每组数据一行,为字符串 SS。

输出格式

每组数据一行输出一个正整数表示最少的代价。

7 
c
aaaab
bbaaaacc
ababa
abba
baab
aaabacdbbdcabaaaaaaaaaaaab
1 
4 
7 
5 
3 
3
18

样例解释

{} -> c,代价为 11;

{} -> aa -> aaaa -> aaaab,代价为 2+1+1=42 + 1 + 1 = 4;

{} -> aa -> aaaa -> aaaacc -> bbaaaac,代价为 2+1+2+2=72 + 1 + 2 + 2 = 7;

{} -> ababa,代价为 55;

{} -> ab -> abba,代价为 2+1=32 + 1 = 3;

{} -> ab -> baab,代价为 2+1=32 + 1 = 3;

{} -> aaa -> aaaaaa -> baaaaaa -> baaaaaaaaaaaab -> aaabacdbbdcabaaaaaaaaaaaab, 代价为 3+1+1+1+12=183 + 1 + 1 + 1 + 12 = 18。

数据规模与约定

对于 100%100\% 的数据,1≤T≤101\leq T\leq 10,1≤∣S∣≤1051\leq |S|\leq 10^5。