首先，对于 \(Y_S(L)\)，字典序最小，只需要在后缀数组 \(\newcommand{\sa}{\mathrm{sa}}\newcommand{\height}{\mathrm{height}}\sa\) 中找到最小的 \(i\) 满足 \(n-\sa_i+1 \ge L\)。
然而又要求左端点最小。
注意到由于后缀数组是按照字典序排序的，所以如果某些后缀的前 \(L\) 个字符相等，也就是 LCP 的长度不小于 \(L\)，则它们在后缀数组中一定是连续的。
又因为 \(i\) 是最小的，所以别的这些前 \(L\) 个字符相等的后缀一定在 \(i\) 之后。
考虑到 \(\height\) 数组的性质：两个后缀的 LCP 长度相当于其在后缀数组的排名间的 RMQ。
则由于 RMQ 具有单调性，可以二分来找这个区间的右端点。
找到之后，只需要对后缀数组上这一段在原串中的下标求个最小值就行了。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
const int N = 3e5;
const int M = 1e7 + 1;
const int LG = 19;
int sig,n,a[N + 5];
int lg2[N + 5];
int sa[N + 5],rk[N + 5],tpr[N + 5],c[M + 5],height[N + 5];
int st[2][LG + 5][N + 5];
void build_SA()
{
static int m = sig;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i] = a[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[i]]--] = i;
for(register int w = 1,p = 0;p < n;w <<= 1,m = p)
{
p = 0;
for(register int i = 1;i <= w;++i)
tpr[++p] = n - w + i;
for(register int i = 1;i <= n;++i)
if(sa[i] > w)
tpr[++p] = sa[i] - w;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[tpr[i]]]--] = tpr[i];
swap(rk,tpr),rk[sa[1]] = p = 1;
for(register int i = 2;i <= n;++i)
rk[sa[i]] = tpr[sa[i]] == tpr[sa[i - 1]] && tpr[sa[i] + w] == tpr[sa[i - 1] + w] ? p : ++p;
}
for(register int i = 1,k = 0;i <= n;++i)
{
k -= (bool)k;
for(;a[i + k] == a[sa[rk[i] - 1] + k];++k);
height[rk[i]] = k;
}
}
int query(int op,int l,int r)
{
int lg = lg2[r - l + 1];
return min(st[op][lg][l],st[op][lg][r - (1 << lg) + 1]);
}
int main()
{
scanf("%d%d",&sig,&n),++sig;
if(sig == 27)
{
char ch;
for(register int i = 1;i <= n;++i)
scanf(" %c",&ch),a[i] = ch - 'a' + 1;
}
else
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),++a[i];
build_SA();
for(register int i = 1;i <= n;++i)
st[0][0][i] = height[i],st[1][0][i] = sa[i];
for(register int i = 2;i <= n;++i)
lg2[i] = lg2[i >> 1] + 1;
for(register int i = 1;i <= LG;++i)
for(register int j = 1;j + (1 << i) - 1 <= n;++j)
st[0][i][j] = min(st[0][i - 1][j],st[0][i - 1][j + (1 << i - 1)]),
st[1][i][j] = min(st[1][i - 1][j],st[1][i - 1][j + (1 << i - 1)]);
for(register int L = 1,i = 1,l,r,mid,pos;L <= n;++L)
{
for(;n - sa[i] + 1 < L;++i);
l = i + 1,r = n,pos = i;
while(l <= r)
mid = l + r >> 1,query(0,i + 1,mid) >= L ? (l = mid + 1,pos = mid) : (r = mid - 1);
printf("%d%c",query(1,i,pos)," \n"[L == n]);
}
}