后缀自动机(SAM)板子 -- LG P3804
作者:
nickxiao
,
2022-09-07 16:04:27
,
所有人可见
,
阅读 176
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1e6 + 10;
char str[maxn];
int tot = 1,np = 1,to[maxn << 1][26],link[maxn << 1],len[maxn << 1];
long long res = 0,cnt[maxn << 1];
vector<int>e[maxn << 1];
inline void add(int c){
int p = np;np = ++tot;
len[np] = len[p] + 1,cnt[np] = 1;
while (p && !to[p][c]) to[p][c] = np,p = link[p];
if (!p) link[np] = 1;
else {
int q = to[p][c];
if (len[q] == len[p] + 1) link[np] = q;
else {
int nq = ++tot;
len[nq] = len[p] + 1;
link[nq] = link[q],link[np] = link[q] = nq;
while (p && to[p][c] == q) to[p][c] = nq,p = link[p];
memcpy(to[nq],to[q],sizeof to[q]);
}
}
}
void dfs(int u){
for (int v : e[u])
dfs(v),cnt[u] += cnt[v];
if (cnt[u] > 1) res = max(res,cnt[u] * len[u]);
}
int main(){
scanf("%s",str + 1);
int n = strlen(str + 1);
for (int i = 1 ; i <= n ; ++i)
add(str[i] - 'a');
for (int i = 2 ; i <= tot ; ++i)
e[link[i]].push_back(i);
dfs(1);
printf("%lld",res);
return 0 ;
}