308552: CF1537E2. Erase and Extend (Hard Version)

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Erase and Extend (Hard Version)

题意翻译

你有一个字符串 $s$,你可以进行两种操作。 - 删去字符串的最后一个字符。 - 将 $s$ 变为 $s+s$,$+$ 表示字符串连接,也就是复制一次字符串。 你可以随意的进行操作,也可以不进行操作。 你需要找到 $s$ 进行操作后获得的所有长度为 $k$ 的字符串中**字典序最小**的字符串。

题目描述

This is the hard version of the problem. The only difference is the constraints on $ n $ and $ k $ . You can make hacks only if all versions of the problem are solved. You have a string $ s $ , and you can do two types of operations on it: - Delete the last character of the string. - Duplicate the string: $ s:=s+s $ , where $ + $ denotes concatenation. You can use each operation any number of times (possibly none). Your task is to find the lexicographically smallest string of length exactly $ k $ that can be obtained by doing these operations on string $ s $ . A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a\ne b $ ; - In the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

输入输出格式

输入格式


The first line contains two integers $ n $ , $ k $ ( $ 1 \leq n, k \leq 5\cdot 10^5 $ ) — the length of the original string $ s $ and the length of the desired string. The second line contains the string $ s $ , consisting of $ n $ lowercase English letters.

输出格式


Print the lexicographically smallest string of length $ k $ that can be obtained by doing the operations on string $ s $ .

输入输出样例

输入样例 #1

8 16
dbcadabc

输出样例 #1

dbcadabcdbcadabc

输入样例 #2

4 5
abcd

输出样例 #2

aaaaa

说明

In the first test, it is optimal to make one duplication: "dbcadabc" $ \to $ "dbcadabcdbcadabc". In the second test it is optimal to delete the last $ 3 $ characters, then duplicate the string $ 3 $ times, then delete the last $ 3 $ characters to make the string have length $ k $ . "abcd" $ \to $ "abc" $ \to $ "ab" $ \to $ "a" $ \to $ "aa" $ \to $ "aaaa" $ \to $ "aaaaaaaa" $ \to $ "aaaaaaa" $ \to $ "aaaaaa" $ \to $ "aaaaa".

Input

题意翻译

你有一个字符串 $s$,你可以进行两种操作。 - 删去字符串的最后一个字符。 - 将 $s$ 变为 $s+s$,$+$ 表示字符串连接,也就是复制一次字符串。 你可以随意的进行操作,也可以不进行操作。 你需要找到 $s$ 进行操作后获得的所有长度为 $k$ 的字符串中**字典序最小**的字符串。

加入题单

上一题 下一题 算法标签: