Я, Фишль, принцесса Веруртейлунга, спустилась на эту землю по зову судьбы — О, ты тоже путешественница из другого мира? Очень хорошо, я разрешаю вам путешествовать со мной.
Нет ничего удивительного в том, что Фишль говорит, так странно выбирая выражения. Однако на этот раз даже Оз, ее друг-ворон, не может истолковать их! Может быть, вы поможете нам понять, что говорит эта юная принцесса?
Вам дана строка из \(n\) строчных латинских букв — слово, которое только что произнесла Фишль. Вы думаете, что MEX строки может помочь вам найти смысл этого сообщения. MEX строки определяется как самая короткая строка, которая не встречается как непрерывная подстрока во входных данных. Если существует несколько таких строк, то за MEX считается лексикографически наименьшая из них. Обратите внимание, что пустая подстрока НЕ считается MEX.
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Узнайте, что представляет собой строка MEX!