首页 > 试题广场 > 序列组装
[编程题]序列组装
  • 热度指数:102 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
对于长度为n的字符串str[1..n],假设1<=i,j<=n,定义str[1..i]为str的前缀,str[j..n]为str的后缀。
比如str="abcd",则"a"、"ab"、"abc"和"abcd"都是"abcd"的前缀,"d"、"cd"、"bcd"和"abcd"都是"abcd"的后缀。
如果字符串str2的一个前缀刚好是str1的后缀,那么允许这两个字符串拼接,比如Xabc后面可以拼接上abcYZ
得到X[abc]YZ(中括号表示两个串重叠的部分)。现在给定一系列固定长度的字符串,求它们能拼接成的最短字符串。

举个例子,给定两个字符串ATCC和CCTA,它们可以拼接成ATC[C]CTA, AT[CC]TA, CCT[A]TCC,其中最短的字符串长度是6。

复杂度的说明: O(n^2*(2^n+L))可以通过所有数据。 其他的复杂度如果优化得当,也可以得分
时限维持1s

输入描述:
第一行一个正整数T,表示T个测试样例;
对于每个测试样例,
输入正整数n(n<=10)和l(l<=1e4),分别表示字符串个数n,以及字符串的长度l(字符串只包含数字和字母);
接下来n行,输入n个字符串。


输出描述:
输出T行,每行一个正整数,表示每个样例能得到的最短拼接长度
示例1

输入

1
2 4
ATCC
CCTA

输出

6

备注:
有60%的数据满足 L<=100

这道题你会答吗?花几分钟告诉大家答案吧!