CF1537E2 Erase and Extend (Hard Version)

这是该问题的困难版本。唯一的区别在于 $n$ 和 $k$ 的约束条件。只有在所有版本的问题都被解决后，你才能进行 hack。 你有一个字符串 $s$，你可以对它进行两种操作： - 删除字符串的最后一个字符。 - 复制字符串：$s := s + s$，其中 $+$ 表示连接操作。 每种操作你都可以使用任意次数（也可以一次都不用）。 你的任务是，通过对字符串 $s$ 进行上述操作，得到长度恰好为 $k$ 的字典序最小的字符串。 如果满足以下任意一条，字符串 $a$ 的字典序小于字符串 $b$： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 在 $a$ 和 $b$ 第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 5 \cdot 10^5$），分别表示原始字符串 $s$ 的长度和所需字符串的长度。 第二行包含字符串 $s$，由 $n$ 个小写英文字母组成。

输出通过上述操作可以得到的长度恰好为 $k$ 的字典序最小的字符串。

在第一个测试样例中，最优方案是进行一次复制操作："dbcadabc" $\to$ "dbcadabcdbcadabc"。 在第二个测试样例中，最优方案是先删除最后 $3$ 个字符，然后复制字符串 $3$ 次，再删除最后 $3$ 个字符，使字符串长度为 $k$。 "abcd" $\to$ "abc" $\to$ "ab" $\to$ "a" $\to$ "aa" $\to$ "aaaa" $\to$ "aaaaaaaa" $\to$ "aaaaaaa" $\to$ "aaaaaa" $\to$ "aaaaa"。 由 ChatGPT 4.1 翻译