P3804 【模板】后缀自动机

题目描述

给定一个只包含小写字母的字符串$S$ ,

请你求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。

输入输出格式

一行一个仅包含小写字母的字符串$S$

一个整数，为 所求答案

输入输出样例

abab

4

说明

对于$10\%$ 的数据，$|S|<=1000$

对于$100\%$ 的数据，|S|<=10^6

$|S|<=10$
^6

题解：后缀自动机模板。

代码：

#include<bits/stdc++.h>
using namespace std;
int c[2000001],la,cnt,a[2000001],l[4000001],ch[4000001][26],size[2000001],fa[2000001];
long long ans;
void build(char s){int p=la,np=++cnt;la=np;l[np]=l[p]+1;for(;p&&!ch[p][s];p=fa[p])ch[p][s]=np;if(!p)fa[np]=1;else{int q=ch[p][s];if(l[q]==l[p]+1)fa[np]=q;else{int nq=++cnt;l[nq]=l[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;ch[p][s]==q;p=fa[p])ch[p][s]=nq;}}size[np]=1; 
}
int main(){char s[1000001];int i;scanf("%s",&s);la=cnt=1;for(i=0;s[i];i++)build(s[i]-'a');for(i=1;i<=cnt;i++)c[l[i]]++;for(i=1;i<=cnt;i++)c[i]+=c[i-1];for(i=1;i<=cnt;i++)a[c[l[i]]--]=i;for(i=cnt;i;i--){int p=a[i];size[fa[p]]+=size[p];if(size[p]>1)ans=max(ans,(long long)size[p]*l[p]);}printf("%lld",ans);
}