#P12115. [NWRRC2024] Keyboard Chaos
[NWRRC2024] Keyboard Chaos
Description
你是否曾觉得普通的平面键盘太过无聊,想要设计些更有趣的东西?
一个叫 Kevin 的小男孩设计了一个有 个特殊按键的键盘。每个按键 初始包含一个字母序列:。序列中可能有重复字母。每个字母都是前 个小写英文字母之一。
每次按下按键 时,会输入其序列的第一个字母,并立即将该字母移到序列末尾。因此,第一次按下按键 时输入字母 ,序列变为 ;第二次按下时输入 ,序列变为 ,以此类推。
例如,假设按键 的序列是 , , ,按键 的序列是 , 。若按顺序按下 ,将输入字符串 。
请帮助 Kevin 评估他的键盘功能,找出从初始状态开始,该键盘无法输入的最短字符串(仅由前 个小写字母组成)。
Input Format
第一行包含两个整数 和 ,分别表示按键数量和字母表大小(;)。
接下来的 行中,第 行包含字符 ,表示按键 的初始字母序列()。每个字符都是前 个小写英文字母之一。
Output Format
输出该键盘从初始状态开始无法输入的最短字符串(由前 个小写字母组成)。若有多个最短字符串,输出任意一个即可。
若可以输入所有可能的字符串,则输出单个字符串 。
1 26
win
f
3 3
abc
bca
cab
aa
4 2
aab
bb
a
bab
NO
Hint
在第一个测试用例中,键盘只能输入 的前缀。由于无法以 以外的字母开头,任何非 的小写字母都是正确答案。
在第二个测试用例中, 和 也是可能的正确答案。
京公网安备 11011102002149号