#P6885. 字符串问题

    ID: 6716 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理二分答案字符串后缀数组倍增计数排序Kasai 算法图论Kahn 算法动态规划DAG 动态规划枚举与搜索路径恢复CF2500

字符串问题

字符串问题(string)

题目背景

记 ∣S∣|S| 为字符串 SS 的长度,S(i)S(i) 为从左至右第 ii 个字符。S(L,R)S(L,R) 表示第 LL 至第 RR 个字符组成的子串;若 L<1L<1、R>∣S∣R>|S| 或 L>RL>R,则约定它为空串。

两个字符串相等,当且仅当长度相同且每个对应位置的字符相同。TT 是 SS 的子串,当且仅当存在 L,RL,R 使 S(L,R)=TS(L,R)=T。

比较两个不相等字符串的字典序:空串小于任何非空串;两个非空串的首字符不同时按首字符比较,否则去掉相同首字符后继续比较。

题目描述

给定 mm 个仅含小写字母的非空模式串 S1,…,SmS_1,\ldots,S_m。

若字符串的每个长度为 KK 的子串,都是至少一个模式串的子串,就称该字符串为 KK-Yazid 串。若字符串长度小于 KK,该条件自然成立。

例如,仅有模式串 abac 时,babac 是 22-Yazid 串,而 abc 不是,因为 bc 不是模式串的子串。

求最小的正整数 kk,使得不存在长度超过 ∑i=1m∣Si∣\sum_{i=1}^{m}\lvert S_i\rvert 的 kk-Yazid 串。

对于这个 kk,再求长度最大的 kk-Yazid 串中字典序最小的字符串 TT。

输入格式

第一行一个非负整数 tt,表示数据组数。

每组数据的第一行一个正整数 mm;接下来 mm 行,每行一个仅包含小写字母的非空字符串 SiS_i。

输出格式

每组数据输出两行:第一行输出最小的正整数 kk,第二行输出所求字符串 TT。若 TT 为空串,则第二行输出空行。

样例输入

2
1
abac
5
abc
bcd
zab
xab
yab

样例输出

3
abac
2
xabcd

样例解释

第一组中,babac 是长度超过 44 的 22-Yazid 串,而不存在长度超过 44 的 33-Yazid 串。

第二组中,xabcd 和 yabcd 都是满足条件的最长 22-Yazid 串,前者字典序更小。

其他样例

样例二见原题下发文件 string/string2.in 和 string/string2.ans。

数据范围

0≤t≤50\le t\le5。每组数据满足 1≤∑i=1m∣Si∣≤2×1051\le\sum_{i=1}^{m}\lvert S_i\rvert\le2\times10^5,因而 1≤m≤2×1051\le m\le2\times10^5。

测试点编号 ∑i=1m∣Si∣≤\sum_{i=1}^{m}\lvert S_i\rvert\le 其他限制
1,21,2 10001000 每个 ∣Si∣=2\lvert S_i\rvert=2
3,43,4 100100 无
5,65,6 10001000
7,87,8 2×1052\times10^5 所有模式串仅包含 a 和 b
9,109,10 无

提示

请注意 k>max⁡1≤i≤m∣Si∣k>\max_{1\le i\le m}\lvert S_i\rvert 时第二问的答案。