Day \(\mathbb P_1^2 + \mathbb P_2^2 + \mathbb P_3^2\)。
不考虑左端点最小，如何求出一个字典序最小子串，只需要建出后缀数组后找最小的 \(i\) 满足 \(n-\text{sa}_i+1\ge L\)，然后取 \(S[\text{sa}_i,\text{sa}_i+L-1]\) 即可。
现在的问题在于可能存在一个 \(j>i\) 使得 \(S[\text{sa}_i,\text{sa}_i+L-1]=S[\text{sa}_j,\text{sa}_j+L-1]\)，并且 \(\text{sa}_i>\text{sa}_j\)，这样的话 \(S[\text{sa}_j,\text{sa}_j+L-1]\) 的左端点就更小了。
但是注意到 \(\text{sa}\) 是按照字典序排序的，也就是说，\(\text{lcp}(S[\text{sa}_i,n],S[\text{sa}_j,n])\) 在 \(i\) 固定时随着的 \(j\) 递增而单调不升，那么合法的 \(j\) 是一段以 \(i\) 为左端点的区间 \([i,p]\)。如果我们求出了这个区间，我们就查询 \(k\in[i,p]\) 的 \(\text{sa}_k\) 的最小值即可。
由于两个后缀 \(S[\text{sa}_i,n],S[\text{sa}_j,n]\) 的 LCP 长度相当于 \(\min\limits_{k\in [i+1,j]}\text{height}_k\)，所以处理出 \(\text{height}\) 数组后建 ST 表支持 \(O(1)\) RMQ，然后直接二分右端点 \(p\) 找到最小的 \(p\) 满足 \(\text{lcp}(S[\text{sa}_i,n],S[\text{sa}_j,n])\ge L\) 就做完了。
复杂度 \(O(n\log n)\)。
// Problem: P5108 仰望半月的夜空
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5108
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
const int M = 25;
const int N = 3e5 + 200;
int n, m, len, t[N], s[N];
int sa[N], rk[N], id[N], ct[N], h[N];
void rst() {
memset(ct, 0, sizeof(int) * (m + 5));
for (int i = 1; i <= n; i++) ct[rk[i]]++;
for (int i = 1; i <= m; i++) ct[i] += ct[i - 1];
for (int i = n; i; i--) sa[ct[rk[id[i]]]--] = id[i];
}
void SA() {
rst();
for (int w = 1, p = 0; w <= n && p != n; w <<= 1, m = p) {
p = 0;
for (int i = n - w + 1; i <= n; i++) id[++p] = i;
for (int i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w;
rst(), swap(rk, id), p = rk[sa[1]] = 1;
for (int i = 2; i <= n; i++) rk[sa[i]] = (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + w] == id[sa[i - 1] + w]) ? p : ++p;
}
for (int i = 1, j = 0; i <= n; i++) {
if (j) j--;
while (s[i + j] == s[sa[rk[i] - 1] + j]) j++;
h[rk[i]] = j;
}
}
struct ST {
int f[N][M];
void init(int *s) {
for (int i = 1; i <= n; i++) f[i][0] = s[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int qry(int l, int r) {
int len = __lg(r - l + 1);
return min(f[l][len], f[r - (1 << len) + 1][len]);
}
} S, T;
void solve() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
if (m == 26) {
char ch; cin >> ch;
s[i] = ch - 'a' + 1;
} else cin >> s[i];
t[++len] = s[i], id[i] = i;
}
sort(t + 1, t + len + 1), len = unique(t + 1, t + len + 1) - t - 1;
for (int i = 1; i <= n; i++) rk[i] = s[i] = lower_bound(t + 1, t + len + 1, s[i]) - t;
m = len + 1, SA(), S.init(h), T.init(sa);
for (int p = 1, i = 1; p <= n; p++) {
while (sa[i] > n - p + 1) i++;
int pos = i;
for (int l = i + 1, r = n; l <= r; ) {
int md = (l + r) >> 1;
if (S.qry(i + 1, md) >= p) pos = md, l = md + 1;
else r = md - 1;
}
cout << T.qry(i, pos) << ' ';
}
}
bool Med;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}