Erase and Extend (Hard Version)
Contest: Codeforces Round 726 (Div. 2)
Difficulty rating: 2200
Tags: binary search, data structures, greedy, hashing, string suffix structures, strings, two pointers

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$$$.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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".

Example input:
8 16
dbcadabc

Example output:
dbcadabcdbcadabc

Example input:
4 5
abcd

Example output:
aaaaa

Editorial:
We know that the final string is some prefix repeated a bunch of times. Incrementally for i from 1 to n we will keep the longest among the first i prefixes that gives the best answer we've seen so far.
So assume the m-th prefix is currently the best and we're considering position p. If the p-th character is greater than the corresponding character in s[1..m] * (a lot) then the p-th prefix and any further prefixes can't possibly give a smaller answer, so we just print the current one and finish. Otherwise all the characters before the p-th are all less than or equal to the corresponding characters in s[1..m] * (lots), so if the p-th is smaller than the corresponding we set the p-th prefix as the best.
Now the interesting case is if the current character is the same as the corresponding one. Say then that p = m + k, by the logic of the previous paragraph we must have s[(m + 1)..(m + k)] = s[1..k]. If k = m then the new prefix is just the old one twice, so set p as the best prefix now. This ensures that otherwise k < m.
Denote A = s[1..k] and B = s[(k + 1)..m], so the string formed by the current best prefix is ABABABABA... and the new one is ABAABAABA... Now if AB = BA then these strings are in fact the same, so set m + k as the new best prefix. Otherwise we can find the first position where AB and BA differ, and use that to determine whether the new prefix is better. This can be done in O(1) with Z function, thus giving a linear solution for the full problem.