题目地址:https://www.luogu.org/problem/P3804
解题思路:
对于此题求拓扑序的两种方法:
(1)桶排序法:最终y[x]=i, 表示在拓扑序中第x个点是i
void _count()
{
memset(x,0,sizeof(x));
for(int i=1;i<=cnt;i++) x[len[i]]++;
for(int i=1;i<=cnt;i++) x[i]+=x[i-1];/
for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
for(int i=cnt;i>=1;i--)
cnt[link[y[i]]]+=cnt[y[i]];
}
(2)dfs
vector<int> v[MAXN];
LL ans = 0;
for(int i = 2; i <= tot; i++) v[link[i]].push_back(i);
void dfs(int x) {
for(int i = 0; i < v[x].size(); i++)
dfs(v[x][i]), cnt[x] += cnt[v[x][i]];
if(siz[x] > 1) ans = max(ans, 1ll * cnt[x] * maxlen[x]);
}
例如字符串aabbabd,建立的SAM和拓扑序(红色箭头路线)为:
图源:https://www.cnblogs.com/zjp-shadow/p/9218214.html
ac代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+100;
int maxlen[maxn<<1], trans[maxn<<1][30], link[maxn<<1];
int x[maxn<<1], y[maxn<<1], cnt[maxn<<1];
int num, last;//num表示状态数
char s[maxn];
void init()
{
num = last = 1;//起始状态的编号为1
maxlen[last] = link[last] = 0;//起始位置为空字符,长度为0
}
void insert(int id)
{
int z = ++num, p;
maxlen[z] = maxlen[last]+1;
for(p = last; p && !trans[p][id]; p = link[p]) trans[p][id] = z;
if(!p) link[z] = 1;//路径上不存在跳转
else//连接路径上已存在跳转
{
int x = trans[p][id];//第一个存在跳转的状态跳转去的状态
if(maxlen[x] == maxlen[p]+1) link[z] = x;//一个
else//多个
{
int y = ++num;
maxlen[y] = maxlen[p]+1;
memcpy(trans[y], trans[x], sizeof(trans[x]));
link[y] = link[x];
for(; p && trans[p][id] == x; p = link[p]) trans[p][id] = y;
link[x] = link[z] = y;
}
}
last = z;
cnt[z] = 1;
}
void count()
{
memset(x, 0, sizeof x);
for(int i = 1; i <= num; i++) x[maxlen[i]]++;
for(int i = 1; i <= num; i++) x[i] += x[i-1];
for(int i = 1; i <= num; i++) y[x[maxlen[i]]--] = i;
for(int i = num; i >= 1; i--)
cnt[link[y[i]]] += cnt[y[i]];
}
int main()
{
scanf("%s", s);
int len = strlen(s);
init();
for(int i = 0; i < len; i++) insert(s[i]-'a');
count();
ll ans = 0;
for(int i = 1; i <= num; i++)
if(cnt[i] > 1)
ans = max(ans, 1ll*maxlen[i]*cnt[i]);
printf("%lld\n", ans);
return 0;
}