SAM 模板
评价：逆天纸糊串，学不会一点。
#include <bits/stdc++.h>
const int MAXN = 3e6 + 100;
int N;
char ch[MAXN];
long long answer;
class Suffix_Automaton {
private:
int tot, last, root;
int child[MAXN][26], link[MAXN], length[MAXN];
long long cnt[MAXN];
public:
Suffix_Automaton() {
root = tot = last = 1;
}
void Insert(int c) {
int p = last, newP = ++ tot;
last = newP;
length[newP] = length[p] + 1;
cnt[newP] = 1;
while (p && !child[p][c]) {
child[p][c] = newP;
p = link[p];
}
// std::cout << p << '\n';
if (!p) {
link[newP] = root;
}
else {
int q = child[p][c];
if (length[q] == length[p] + 1) {
link[newP] = q;
}
else {
int newQ = ++ tot;
memcpy(child[newQ], child[q], sizeof child[q]);
link[newQ] = link[q];
link[q] = link[newP] = newQ;
length[newQ] = length[p] + 1;
while (p && child[p][c] == q) {
child[p][c] = newQ;
p = link[p];
}
}
}
}
std::vector<int> son[MAXN];
void Build() {
for (int i = 1; i <= tot; ++ i) {
son[link[i]].emplace_back(i);
// std::cout << link[i] << ' ';
}
// std::cout << '\n';
}
void Dfs(int now) {
for (const int &iter: son[now]) {
Dfs(iter);
cnt[now] += cnt[iter];
}
if (cnt[now] != 1) {
answer = std::max(answer, length[now] * cnt[now]);
}
}
}sam;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> (ch + 1);
int N = strlen(ch + 1);
for (int i = 1; i <= N; ++ i)
sam.Insert(ch[i] - 'a');
sam.Build();
sam.Dfs(1);
std::cout << answer << '\n';
return 0;
}