建议先学会 Trie 图和 AC 自动机 了解自动机大概是什么。
后缀自动机SAM
请你求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。
对于题目要求，我们首先要统计所有子串的出现次数，还要记录所有子串的长度。如果暴力枚举字符串复杂度为 $O(n^3)$（$O(n^2)$ 的子串枚举，$O(n^2)$ 的子串每位判断），但是如果处理每个字符的新加入的情况，虽然复杂没变，但是如果放在字典树（$Trie$ 树）上匹配时，是 $O(n^2)$ 的复杂度（叶子节点）。因为从整个字符串的判断，变成了点个字符的判断。
如果要继续优化，那么就要建 $Trie$ 图了。
这里为了更加直观的描述思路，我们讨论的是一个新考虑字符要经历什么。
（如果字体过小，请自行调整网页缩放。）
这里的 $f_a$ 的箭头不是正确的在这里只是解释新插入的点会经历什么，真正的 $f_a$ 会在后面介绍。
上面几个图片记录了三种情况：
之前没出现过这种字符，直接更新到根节点。
之前出现过这种字符，当时“冲突”地点和之前出现的相同字符的位置相邻。
之前出现过这种字符，当时“冲突”地点和之前出现的相同字符的位置不相邻，开新点维护。注意新点的长度的初始化是根据“冲突”地点累计的。
$f_a$ 指向的是前一个相同字符的位置，如果没有就只会根节点。或者是开的新点就像上面最后几张图描述的。
一个串：
$aab$
可以在：
$aabaa$
$aabaabaa$
中存在（后面增加的是不断继续讨论新的字符）。
所以已经存在的一定存在（有点奇怪，但是没问题！）。
在我们建树的时候，会初始化长度，而新的字符在后面形成的短串，其长串一定包含。
那么就可以通过找父节点统计出现的次数，根据字串长度，求权值。
一般情况下，SAM 当成模板背，用的时候直接用即可。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=3e6+10;
char s_s[o_o];//原字符串
long long a_s;//结果统计
int m_p[o_o][30];//存 trie 树
int f_a[o_o];//父节点
int k_k=1;
int s_n=1;//节点编号
int e_d[o_o];//结束长度
int n_m[o_o];//子树大小
struct po{
int v;
int n_t;
}p_p[o_o];
int h_d[o_o];
int x_p;
void a_d(int u,int v){//加边
p_p[++x_p].v=v;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
void i_n(int x,int i){
int l_t=k_k;//记录上一个字符的位置
n_m[k_k=++s_n]=1;//初始化新节点次数
e_d[k_k]=i;//新字符串结尾编号
while(l_t&&m_p[l_t][x]==0){//存在上一个字符，上一个字符没有连接当前字符
m_p[l_t][x]=k_k;//连接字符
l_t=f_a[l_t];//爬祖先，回找
}
if(l_t==0){//达到根节点
f_a[k_k]=1;//特判设置父节点
return;
}
int n_w=m_p[l_t][x];//记录当前位置的字符
if(e_d[l_t]+1==e_d[n_w]){//如果两个节点是相邻的
f_a[k_k]=n_w;//新节点的父亲为当前位置的字符
return;
}
e_d[++s_n]=e_d[l_t]+1;//记录结束编号
for(int i=1;i<=26;i++)m_p[s_n][i]=m_p[n_w][i];//继承节点儿子
f_a[s_n]=f_a[n_w];//继承父节点
f_a[n_w]=s_n;//更新父节点
f_a[k_k]=s_n;//更新父节点
for(int i=l_t;m_p[i][x]==n_w;i=f_a[i])m_p[i][x]=s_n;//更新节点
}
void d_f(int k){
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
d_f(v);
n_m[k]+=n_m[v];//累计每个节点的出现次数
}
if(n_m[k]!=1)a_s=max(a_s,(long long)n_m[k]*e_d[k]);//取最大值
}
int l_s=0;
int main(){
scanf("%s",s_s+1);
l_s=strlen(s_s+1);
for(int i=1;i<=l_s;i++)i_n(s_s[i]-'a'+1,i);
for(int i=2;i<=s_n;i++)a_d(f_a[i],i);//父节点和节点之间加边
d_f(1);
printf("%lld",a_s);//输出答案
return 0;
}统计字符串不同字串
将 SAM 建出后，深搜贡献累计即可（相同的子串都已经合并了）。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<string>
#include<cmath>
#include<map>
#include<unordered_map>
using namespace std;
long long r_r(){
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const long long o_o=1e6+10;
string s;
int k_k=1,c_n=1;
int n_m[o_o];
int m_p[o_o][31];
int f_a[o_o];
int l_n[o_o];
void i_n(int x,int i){
int l_t=k_k;
n_m[k_k=++c_n]=1;
l_n[k_k]=i;
while(l_t&&m_p[l_t][x]==0){
m_p[l_t][x]=k_k;
l_t=f_a[l_t];
}
if(!l_t){
f_a[k_k]=1;
return ;
}
int n_w=m_p[l_t][x];
if(l_n[l_t]+1==l_n[n_w]){
f_a[k_k]=n_w;
return ;
}
l_n[++c_n]=l_n[l_t]+1;
for(int j=1;j<=26;j++)m_p[c_n][j]=m_p[n_w][j];
f_a[c_n]=f_a[n_w];
f_a[n_w]=f_a[k_k]=c_n;
int k=l_t;
while(m_p[k][x]==n_w){
m_p[k][x]=c_n;
k=f_a[k];
}
}
long long a_s[o_o];
long long d_f(int k){//统计，不同字串个数
if(a_s[k])return a_s[k];
for(int i=1;i<=26;i++)
if(m_p[k][i])a_s[k]+=d_f(m_p[k][i])+1;//记录并继续深搜
return a_s[k];//返回结果
}
int main(){
char c=getchar();
while(c>'z'||c<'a')c=getchar();
int i_i=0;
while(c>='a'&&c<='z'){
i_n(c-'a'+1,++i_i);
c=getchar();
}
printf("%lld",d_f(1));//输出结果
return 0;
}
