```
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 12;
char s[1010101];
int read()
{
int s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int n, m, T, nw = 0, ans = 0, b[maxn], sa[maxn], x[maxn], y[maxn], h[maxn], rk[maxn], col[maxn], cnt[maxn], L[110], R[110], head, tail, q[maxn];
void build_SA()
{
int num;
for (register int i = 1; i <= n; ++i)
b[x[i] = s[i]]++;
for (register int i = 1; i <= m; ++i)
b[i] += b[i - 1];
for (register int i = n; i >= 1; --i)
sa[b[x[i]]--] = i;
for (register int k = 1; k <= n; k <<= 1)
{
num = 0;
for (register int i = n; i > n - k; --i)
y[++num] = i;
for (register int i = 1; i <= n; ++i)
if (sa[i] > k)
y[++num] = sa[i] - k;
for (register int i = 0; i <= m; ++i)
b[i] = 0;
for (register int i = 1; i <= n; ++i)
b[x[y[i]]]++;
for (register int i = 0; i <= m; ++i)
b[i] += b[i - 1];
for (register int i = n; i >= 1; --i)
sa[b[x[y[i]]]--] = y[i];
for (register int i = 1; i <= n; ++i)
y[i] = 0;
for (register int i = 1; i <= n; ++i)
swap(x[i], y[i]);
num = 1;
x[sa[1]] = 1;
for (register int i = 2; i <= n; ++i)
x[sa[i]] = (y[sa[i]] != y[sa[i - 1]] || y[sa[i] + k] != y[sa[i - 1] + k]) ? ++num : num;
if (num == n)
return;
m = num;
}
}
void build_height()
{
int k = 0;
for (register int i = 1; i <= n; ++i)
rk[sa[i]] = i;
for (register int i = 1; i <= n; ++i)
{
if (rk[i] == 1)
continue;
if (k)
--k;
int j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && s[i + k] == s[j + k])
++k;
h[rk[i]] = k;
}
}
void build_color()
{
for (register int i = 1; i <= T; ++i)
{
for (register int j = L[i]; j <= R[i]; ++j)
{
col[rk[j]] = i;
}
}
}
void add(int x)
{
if (!col[x])
return;
if (++cnt[col[x]] == 1)
++nw;
}
void del(int x)
{
if (!col[x])
return;
if (--cnt[col[x]] == 0)
--nw;
}
int main()
{
while (~scanf("%s", s + n + 1))
{
L[++T] = n + 1, n += strlen(s + n + 1), R[T] = n++, s[n] = T + 1;
}
m = 128;
build_SA(), build_height(), build_color();
add(1);
int l = 1;
for (register int i = 2; i <= n; ++i)
{
while (head < tail && h[q[tail]] >= h[i])
--tail;
q[++tail] = i;
add(i);
if (nw == T)
{
while (nw == T && l < i)
{
del(l++);
}
add(--l);
}
while (head < tail && q[head] <= l)
{
++head;
}
if (nw == T)
{
ans = max(ans, h[q[head]]);
}
}
cout << ans;
}
```
by MatrixCascade @ 2020-12-14 13:46:39
stO
by ieeqwq @ 2020-12-14 13:55:52
先把for里面的re int i,j,k这种东西全部放到外面，不在在for里面声明
by Boxxxxxx @ 2020-12-14 14:15:58
@[Boxxxxxx](/user/156874) 都什么年头了，还有人讲这种没用的卡常
by AsunderSquall @ 2020-12-14 14:16:57
@[Boxxxxxx](/user/156874) 还是 T
by MatrixCascade @ 2020-12-14 14:18:23
m可以只用26个
by jerry3128 @ 2020-12-14 14:45:48
@[jerry3128](/user/27338) 瓶颈不在基排吧 /yiw ，1e6 的 n 多 100 感觉没啥区别（？）
by MatrixCascade @ 2020-12-14 14:47:51
~~（SA复杂度记错了（（（（~~
by jerry3128 @ 2020-12-14 14:54:51
倍增内部第七个循环不需要，第八个可以直接改成交换数组头指针
by AzusaCat @ 2020-12-14 21:26:58
@[AzusaCat](/user/96912) 昨天卡过了，还是谢谢提醒。
by MatrixCascade @ 2020-12-15 19:58:13