#P6885. 字符串问题
字符串问题
字符串问题(string)
题目背景
记 为字符串 的长度, 为从左至右第 个字符。 表示第 至第 个字符组成的子串;若 、 或 ,则约定它为空串。
两个字符串相等,当且仅当长度相同且每个对应位置的字符相同。 是 的子串,当且仅当存在 使 。
比较两个不相等字符串的字典序:空串小于任何非空串;两个非空串的首字符不同时按首字符比较,否则去掉相同首字符后继续比较。
题目描述
给定 个仅含小写字母的非空模式串 。
若字符串的每个长度为 的子串,都是至少一个模式串的子串,就称该字符串为 -Yazid 串。若字符串长度小于 ,该条件自然成立。
例如,仅有模式串 abac 时,babac 是 -Yazid 串,而 abc 不是,因为 bc 不是模式串的子串。
求最小的正整数 ,使得不存在长度超过 的 -Yazid 串。
对于这个 ,再求长度最大的 -Yazid 串中字典序最小的字符串 。
输入格式
第一行一个非负整数 ,表示数据组数。
每组数据的第一行一个正整数 ;接下来 行,每行一个仅包含小写字母的非空字符串 。
输出格式
每组数据输出两行:第一行输出最小的正整数 ,第二行输出所求字符串 。若 为空串,则第二行输出空行。
样例输入
2
1
abac
5
abc
bcd
zab
xab
yab
样例输出
3
abac
2
xabcd
样例解释
第一组中,babac 是长度超过 的 -Yazid 串,而不存在长度超过 的 -Yazid 串。
第二组中,xabcd 和 yabcd 都是满足条件的最长 -Yazid 串,前者字典序更小。
其他样例
样例二见原题下发文件 string/string2.in 和 string/string2.ans。
数据范围
。每组数据满足 ,因而 。
| 测试点编号 | 其他限制 | |
|---|---|---|
| 每个 | ||
| 无 | ||
所有模式串仅包含 a 和 b |
||
| 无 |
提示
请注意 时第二问的答案。