填空题
序列组装
发布于 2022-03-03 17:06:32
对于长度为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。
对于每个测试样例，
输入正整数n（n<=10）和l（l<=1e4），分别表示字符串个数n，以及字符串的长度l（字符串只包含数字和字母）；
接下来n行，输入n个字符串。输入样例： 1 2 4 ATCC CCTA 输出描述： 输出T行，每行一个正整数，表示每个样例能得到的最短拼接长度输出样例 6
比如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个测试样例；时限维持1s
对于每个测试样例，
输入正整数n（n<=10）和l（l<=1e4），分别表示字符串个数n，以及字符串的长度l（字符串只包含数字和字母）；
接下来n行，输入n个字符串。输入样例： 1 2 4 ATCC CCTA 输出描述： 输出T行，每行一个正整数，表示每个样例能得到的最短拼接长度输出样例 6
关注者
0
被浏览
10
