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

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

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


-----Examples-----

Input
8 16
dbcadabc
Output
dbcadabcdbcadabc
Input
4 5
abcd
Output
aaaaa


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

Difficulty: HARD
Tags: String algorithms

Sorting

Amortized analysis

Greedy algorithms

Data structures
Skill types: Data structures

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
def solve(N, K, A):
	tok_size = 1
	ti = 0
	i = 1
	while i < N:
		if A[ti] > A[i]:
			ti = 0
			tok_size = i + 1
		elif A[ti] == A[i]:
			ti = (ti + 1) % tok_size
		else:
			break
		i += 1
	tok = A[:tok_size]
	if len(tok) >= K:
		return tok[:K]
	else:
		d = K // len(tok)
		m = K % len(tok)
		return tok * d + tok[:m]
(N, K) = tuple(map(int, input().split()))
A = input()
print(solve(N, K, A))


import math
import random
from collections import Counter, deque
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import heapq

def S():
	return sys.stdin.readline().split()

def I():
	return [int(i) for i in sys.stdin.readline().split()]

def II():
	return int(sys.stdin.readline())

def IS():
	return sys.stdin.readline().replace('\n', '')

def main():
	(n, k) = I()
	s = IS()
	o = s[0]
	if n == 1:
		print(o * k)
		return
	mn = min(n, k)
	idx = 1
	ans_string = o
	while idx < mn:
		el = s[idx]
		if el < o:
			ans_string += el
			idx += 1
		elif el > o:
			break
		else:
			new_idx_1 = 0
			new_idx_2 = idx
			flag = False
			while new_idx_2 < mn - 1:
				new_idx_2 += 1
				new_idx_1 += 1
				if s[new_idx_2] < s[new_idx_1]:
					flag = True
					ans_string += s[idx:new_idx_2]
					idx = new_idx_2
					break
				elif s[new_idx_2] > s[new_idx_1]:
					break
			if not flag:
				break
	_len = idx
	print((ans_string * (k // _len + 1))[:k])
main()


from math import ceil
(n, k) = [int(s) for s in input().split(' ')]
s = input()
prefix_idx = 0
idx = n - 1
for i in range(1, n):
	if s[i] == s[prefix_idx]:
		if idx == n - 1:
			idx = i - 1
		prefix_idx += 1
	elif s[i] < s[prefix_idx]:
		prefix_idx = 0
		idx = n - 1
	else:
		if idx == n - 1:
			idx = i - 1
		break
multiply = ceil(k / (idx + 1))
print((s[:idx + 1] * multiply)[:k])


(n, k) = map(int, input().split())
s = input()
ans = 1
for i in range(n):
	if s[i] < s[i % ans]:
		ans = i + 1
	elif s[i] > s[i % ans]:
		break
print((s[:ans] * (k // ans + 1))[:k])


def readline():
	return map(int, input().split())

def main():
	(n, k) = readline()
	s = list(map(ord, input()))
	if len(s) > k:
		s = s[:k]
	prefix = 0
	i = 0
	for i in range(1, len(s)):
		if s[i] > s[prefix]:
			s = s[:i]
			break
		elif s[i] == s[prefix]:
			prefix += 1
		else:
			prefix = 0
	if prefix:
		s = s[:-prefix]
	s *= (k - 1) // len(s) + 1
	print(''.join(map(chr, s[:k])))
main()


(n, k) = map(int, input().split())
s = input()
l = 0
pos = 1
n = len(s)
while l < n:
	index = l % pos
	if s[l] < s[index]:
		pos = l + 1
		l += 1
	elif s[l] == s[index]:
		l += 1
	else:
		break
res = s[:pos] * (k // pos + 1)
print(res[:k])


(n, m) = input().split()
n = int(n)
m = int(m)
s = str(input())
p = 1
for i in range(1, n):
	if s[i % p] < s[i]:
		break
	if s[i % p] > s[i]:
		p = i + 1
x = m // p
y = m - x * p
print(s[0:p] * x + s[0:y])


(n, q) = map(int, input().split())
string = input()
p = 0
i = 1
while i < len(string):
	if string[i] < string[p]:
		i += 1
		p = 0
	elif string[i] == string[p]:
		i += 1
		p += 1
	else:
		break
st = string[:i - p]
l = len(st)
print(st * (q // l) + st[:q % l])


(n, k) = map(int, input().split())
s = input()
p = -1
i = 0
while i < n:
	if s[i] > s[0]:
		p = i
		break
	elif s[i] == s[0]:
		j = i + 1
		z = 1
		while j < n and z < i and (s[j] == s[z]):
			j += 1
			z += 1
		if j < n and z < i and (s[j] > s[z]):
			p = i
			break
		i = j - 1
	i += 1
if p != -1:
	s = s[:p]
i = len(s) - 1
while i > 0 and s[i] == s[0]:
	i -= 1
s = s[:i + 1]
print(s * (k // len(s)) + s[:k % len(s)])


import itertools

def validate_prefix(s, prefix):
	n = len(s)
	source = 0
	for i in range(prefix, n):
		if s[i] > s[source]:
			return prefix
		elif s[i] == s[source]:
			source += 1
			if source == prefix:
				source = 0
			continue
		assert s[i] < s[source]
		prefix = i + 1
		source = 0
	return prefix

def determine_initial_prefix(s):
	prefix = 1
	while True:
		new_prefix = validate_prefix(s, prefix)
		if new_prefix == prefix:
			break
		prefix = new_prefix
	return prefix

def solve():
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	pref = determine_initial_prefix(s)
	return ''.join(itertools.islice(itertools.cycle(s[:pref]), k))
print(solve())


import math
import os
import random
import re
import sys
from collections import defaultdict

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
(n, k) = get_ints()
s = get_string()
(i, j, x) = (1, 0, 1)
while i < n and i < k:
	if s[i] > s[0]:
		break
	while i < n and s[i] == s[j]:
		i += 1
		j += 1
	if i >= n or (i < n and s[i] > s[j]):
		break
	i += 1
	j = 0
	x = i
ans = s[:x]
while len(ans) < k:
	ans += ans
ans = ans[:k]
sys.stdout.write(ans + '\n')


from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
from sys import stdin
input = stdin.readline
mp = lambda : map(int, input().split())
it = lambda : int(input())
ls = lambda : list(input().strip())
mt = lambda r: [ls() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def fibo_n(n):
	return ((1 + sqrt(5)) / 2) ** n / sqrt(5)
(a, b) = mp()
s = input().strip()
start = 0
end = 1
finalend = 1
while end != a:
	if s[start] > s[end]:
		finalend = end + 1
		start = 0
		end += 1
	elif s[start] == s[end]:
		start += 1
		end += 1
	else:
		break
st = s[:finalend]
print((st * ceil(b / len(st)))[:b])


import sys
(n, q) = map(int, sys.stdin.readline().split())
string = sys.stdin.readline().rstrip()
p = 0
i = 1
while i < len(string):
	if string[i] < string[p]:
		i += 1
		p = 0
	elif string[i] == string[p]:
		i += 1
		p += 1
	else:
		break
st = string[:i - p]
l = len(st)
answer = st * (q // l)
answer += st[:q % l]
print(answer)


(n, k) = map(int, input().split())
s = input()
p = 0
i = 1
while i < len(s):
	if s[i] < s[p]:
		i += 1
		p = 0
	elif s[i] == s[p]:
		i += 1
		p += 1
	else:
		break
r = s[:i - p]
l = len(r)
print(r * (k // l) + r[:k % l])


def bestPrefix(S):
	best = S[0]
	for i in range(1, len(S)):
		ch = i % len(best)
		if best[ch] < S[i]:
			break
		elif best[ch] > S[i]:
			while len(best) < i + 1:
				best += S[len(best)]
	return best

def solve(s, n, k):
	pref = bestPrefix(s)
	ans = ''
	while len(ans) + len(pref) <= k:
		ans += pref
	ans += pref[:k - len(ans)]
	return ans
(n, k) = map(int, input().split())
s = input()
ans = solve(s, n, k)
print(ans)


(n, m) = list(map(int, input().strip().split()))
(s, z, j) = (input(), '', 1)
for i in range(1, n):
	if s[i] < s[i % j]:
		j = i + 1
	elif s[i] != s[i % j]:
		break
for i in range(0, m):
	z += s[i % j]
print(z)


def bestPref(s):
	pref = s[0]
	for i in range(1, len(s)):
		ind = i % len(pref)
		if pref[ind] < s[i]:
			break
		elif pref[ind] > s[i]:
			while len(pref) < i + 1:
				pref += s[len(pref)]
	return pref

def solve(n, k, s):
	pref = bestPref(s)
	cur = ''
	while len(cur) + len(pref) <= k:
		cur += pref
	cur += pref[:k - len(cur)]
	return cur
(n, k) = list(map(int, input().split()))
ans = solve(n, k, input())
print(ans)


import sys
import os
if 'CP_LOCAL' in os.environ:
	sys.stdin = open('codeforces/input.txt', 'r')
	sys.stdout = open('codeforces/output.txt', 'w')
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, k) = inlt()
alp = insr()
mc = 0
ct = 1
(l, r) = (0, len(alp) - 1)
for i in range(1, len(alp)):
	if alp[i] > alp[mc]:
		break
	ct += 1
	if alp[i] == alp[mc]:
		mc += 1
	else:
		mc = 0
while mc:
	ct -= 1
	mc -= 1
sub = ''.join(alp[:ct])
res = sub[:k]
while len(res) < k:
	res += res
print(res[:k])


(n, k) = map(int, input().split())
s = input()
l = ''
l = l + s[0]
j = 0
for i in range(1, n):
	if s[i] > l[j]:
		break
	elif s[i] < l[j]:
		l = l + s[i]
		j = 0
	elif s[i] == l[j]:
		l = l + s[i]
		j = j + 1
p = len(l)
r = l[:p - j]
m = len(r)
s = r * (k // m)
for i in range(k % m):
	s = s + r[i]
print(s)


from io import BytesIO, IOBase
import math
import time
import sys
import os
from math import gcd, floor, sqrt, log
start_time = time.time()

def iin():
	return int(input())

def sin():
	return input().strip()

def listin():
	return list(map(int, input().strip().split()))

def liststr():
	return list(map(str, input().strip().split()))

def ceill(x):
	return int(x) if x == int(x) else int(x) + 1

def ceilldiv(x, d):
	return x // d if x % d == 0 else x // d + 1

def LCM(a, b):
	return a * b // gcd(a, b)
(n, m) = listin()
s = sin()
z = ''
j = 1
for i in range(1, n):
	if s[i] < s[i % j]:
		j = i + 1
	elif s[i] != s[i % j]:
		break
for i in range(0, m):
	z += s[i % j]
print(z)


import math, bisect
(n, k) = map(int, input().split())
a = input()
ind1 = 0
x = 0
ind2 = 1
z = 1
ans = a
while ind2 != n:
	if a[ind1] == a[ind2]:
		if x == 0:
			z = ind2
			x = 1
		ind1 += 1
	elif a[ind1] > a[ind2]:
		x = 0
		z = ind2 + 1
		ind1 = 0
	else:
		break
	ind2 += 1
ans = a[:z]
b = ''
l = len(ans)
for i in range(k):
	b += ans[i % l]
print(b)


from math import *
(n, k) = [int(i) for i in input().split()]
a = input()
b = (a * ceil(k / n))[:k]
ci = 0
mb = -1
ind = -1
for i in range(1, k):
	if ord(b[ci]) < ord(b[i]):
		ind = i
		if mb != -1:
			ind = mb
		break
	elif ord(b[ci]) == ord(b[i]):
		ci += 1
		if mb == -1:
			mb = i
	elif ord(b[ci]) > ord(b[i]):
		ci = 0
		mb = -1
ans = ''
if ind == -1:
	ans = b
else:
	c = b[:ind]
	ans = (c * ceil(k / ind))[:k]
print(ans)


import sys
f = sys.stdin

def line():
	return f.readline().strip().split()

def solve():
	pos = 1
	stop = False
	i = 1
	while i < len(W):
		off = 0
		for j in range(pos):
			if i + j == len(W) or W[i + j] > W[j]:
				stop = True
				break
			off += 1
			if W[i + j] != W[j]:
				break
		if not stop:
			pos += off
		i = pos
		if stop:
			break
	pref = W[:pos]
	return pref
T = 1
for test in range(1, T + 1):
	(N, K) = map(int, line())
	W = line()[0]
	if K < N:
		W = W[:K]
	pref = solve()
	sz = len(pref)
	c = 0
	m = K // sz
	res = ''.join((pref for _ in range(m)))
	res += pref[:K % sz]
	sys.stdout.write(res)
	sys.stdout.write('\n')
f.close()


(n, k) = map(int, input().split())
s = input()
p = ''
p += s[0]
j = 1
for i in range(1, len(s)):
	if s[i] > s[i % j]:
		break
	if s[i] < s[i % j]:
		j = i + 1
ans = ''
for i in range(0, k):
	ans += s[i % j]
print(ans)


(n, k) = [int(d) for d in input().split()]
s = input()
if len(s) == 1:
	print(s * k)
else:
	x = s[0]
	done = True
	i = 1
	get = False
	idx = 0
	curr = 0
	while i < len(s) and done == True:
		if s[i] < s[curr]:
			x = x + s[i]
			if curr != 0:
				curr = 0
				get = False
			i = i + 1
		elif s[i] == s[curr]:
			x = x + s[i]
			curr = curr + 1
			if get == False:
				idx = i
				get = True
			i = i + 1
		else:
			break
	if get == True:
		x = x[:idx]
	full = k // len(x)
	rem = k - full * len(x)
	res = x * full + x[:rem]
	print(res)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(1):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	(l, r) = (0, 0)
	ans = ''
	for i in range(k):
		if s[l] >= s[r]:
			if ans and s[l] == s[r]:
				l += 1
			else:
				l = 0
			ans += s[r]
		else:
			ans += s[l]
			r = l
			l = 0
		r += 1
		r %= n
		l %= n
	print(ans)


from cmath import log
(n, k) = input().split()
n = int(n)
k = int(k)
s = input()
shortest_len = 0
curr_cmp = 0
last_char = '~'
first = s[0]
for i in range(n):
	if curr_cmp > 0 and s[curr_cmp] == s[i]:
		curr_cmp += 1
	elif curr_cmp and s[curr_cmp] > s[i]:
		curr_cmp = 0
	elif curr_cmp or (s[i] > last_char and s[i] > first):
		break
	elif s[i] > last_char and s[i] == first:
		curr_cmp += 1
	last_char = s[i]
	shortest_len += 1
shortest_len -= curr_cmp
cut = s[0:shortest_len]
for i in range(int(k / shortest_len)):
	print(cut, end='')
print(s[0:int(k % shortest_len)])


(n, k) = map(int, input().split())
s = input()
unit = s[0]
while True:
	i = 0
	test = s + unit
	while i < len(s) and unit == test[i:i + len(unit)]:
		i += len(unit)
	while i < len(s) and unit > test[i:i + len(unit)]:
		i += 1
	if i == len(unit):
		break
	unit = test[:i]
print(unit * (k // len(unit)) + unit[:k % len(unit)])


def sec(init, i, e, flag):
	i1 = i
	while i < n and ord(s[init]) == ord(s[i]) and (init < i1):
		init += 1
		i += 1
		e += 1
	if i == n or (i != n and ord(s[init]) < ord(s[i])):
		flag = 1
	return (e, flag, i)
(n, k) = map(int, input().split())
s = input()
init = 0
e = 1
i = 1
flag = 0
while i < n:
	if ord(s[i]) > ord(s[init]):
		break
	elif s[i] == s[init]:
		e1 = e
		(e, flag, i) = sec(init, i, e, flag)
		if flag == 1:
			e = e1
			break
		else:
			init = 0
			continue
	e += 1
	i += 1
t = k // e + 1
s = s[:e]
x = s
for i in range(t):
	s += x
print(*s[:k], sep='')


inp = input().split()
length = int(inp[0])
required = int(inp[1])
s = input()
count = 1
for i in range(1, length):
	if s[i] > s[i % count]:
		break
	if s[i] < s[i % count]:
		count = i + 1
for i in range(required):
	print(s[i % count], end='')


(n, desired) = map(int, input().split())
s = list(input())
stack = [s[0]]
ptr = 0
for i in range(1, n):
	if ptr == len(stack):
		ptr = 0
	if s[i] < stack[ptr]:
		stack.append(s[i])
		ptr = 0
	elif s[i] == stack[ptr]:
		stack.append(s[i])
		ptr += 1
	else:
		stack = stack[:len(stack) - ptr]
		break
while stack[-1] == stack[0] and len(stack) > 1:
	stack.pop()
ans = []
for i in range(desired):
	ptr = i % len(stack)
	ans.append(stack[ptr])
print(*ans, sep='')


def zfunction(s):
	n = len(s)
	z = [0] * n
	z[0] = n
	(R, L) = (0, 0)
	for i in range(1, n):
		if i > R:
			L = i
			R = i
			while R < n and s[R - L] == s[R]:
				R += 1
			z[i] = R - L
			R -= 1
		else:
			k = i - L
			if z[k] < R - i + 1:
				z[i] = z[k]
			else:
				L = i
				while R < n and s[R - L] == s[R]:
					R += 1
				z[i] = R - L
				R -= 1
	return z
(n, k) = map(int, input().split())
s = input()
z = zfunction(s)
best = 0
for i in range(1, n):
	comp = i - best - 1
	if s[i] > s[comp]:
		break
	if s[i] < s[comp]:
		best = i
	elif comp + comp + 1 == i:
		best = i
	else:
		check = z[comp + 1]
		if check >= best + 1:
			best = i
		elif s[comp + 1 + check] > s[check]:
			best = i
s = s[:best + 1]
while len(s) < k:
	s = s + s
s = s[:k]
print(s)