Erase and Extend (Hard Version)
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$$$. 
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".
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$$$.
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]
if __name__ == '__main__':
    (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])
if __name__ == '__main__':
    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])