#6174. 「美团 CodeM 初赛 Round B」合并字符串的价值

内存限制:256 MiB 时间限制:300 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

输入两个串 a,b ,你需要把 a,b 组合成一个串 c ,使得 |c|=|a|+|b| c 可以拆成两个没有重复元素的子序列的并,使得一个子序列为 a ,另一个子序列为 b 。 一个字符串 s 的价值定义如下( n=|s|>1 ):

枚举所有的分界线 1 \leq k \leq n-1 ,令 u=s_{[1,k]},v=s_{[k+1,n]} ,将 u,v 的字符重新排列使得 u,v 的最长公共前缀最大,所有可能的分界线中 u,v 的最长公共前缀的最大值就是这个字符串的价值。

例如字符串 \texttt{ACGTTTGCAT} 的价值为 5 ,因为均分成两半之后得到 u=\texttt{ACGTT},v=\texttt{TGCAT} ,重新排列之后可以做到 u=v 即最长公共前缀为 5

你需要求出所有可能的 c 中价值最大的字符串,输出这个最大价值即可。

输入格式

第一行一个整数 T

接下来 2T 行,每两行两个字符串分别代表 a,b

输出格式

对于每组数据输出一行一个整数表示价值最大的 c 的价值。

样例

样例输入

2
ACGT
ACGT
AACCGGTT
ACACAGAT

样例输出

4
7

数据范围与提示

T \leq 500

|a|,|b| \leq 100,000;\sum |a|+|b| \leq 500,000

a,b 的字符集为 \{\texttt{A,C,G,T}\}