CF196D The Next Good String

在有关字符串的问题中，我们常常需要找到具有某种特性的字符串。出题人不想在想一个新名字上浪费时间，于是就把这种字符串叫做“好串”。如果一个字符串中不存在长度大于等于 $d$ 的回文子串，我们称它为好串。 给定一个只包含小写英文字母的字符串 $s$，请找出一个长度为 $|s|$、只包含小写英文字母、字典序大于 $s$ 的好串 $t$。在所有满足条件的字符串中，$t$ 需要是字典序最小的。 我们称非空字符串 $s[a\, ...\, b]=s_{a}s_{a+1}\cdots s_{b}$（$1\le a\le b\le |s|$）为字符串 $s=s_{1}s_{2}\cdots s_{|s|}$ 的子串。 非空字符串 $s=s_1s_2\cdots s_n$ 被称为回文字符串，当且仅当对所有 $1\le i\le n$，都有 $s_i=s_{n-i+1}$。换句话说，回文串正着和反着读都相同。 字符串 $x=x_1x_2\cdots x_{|x|}$ 的字典序大于字符串 $y=y_1y_2\cdots y_{|y|}$，当且仅当： - 要么 $|x|>|y|$，且 $x_1=y_1,\ x_2=y_2,\ \ldots,\ x_{|y|}=y_{|y|}$； - 要么存在某个 $r$（$r

第一行输入一个整数 $d$（$1\le d\le |s|$）。 第二行输入一个非空字符串 $s$，其长度不超过 $4\times 10^5$。该字符串仅由小写英文字母组成。

输出一个长度与 $s$ 相同、字典序大于 $s$ 的好串。如果不存在这样的字符串，输出 “Impossible”。

由 ChatGPT 5 翻译