以此纪念我都快忘了的后缀自动机（捂脸）
不过这题有两种做法：
用后缀自动机，先把原串再接遍中间加入特殊连接字符再把原串反接两遍，对这个新构造出的串做后缀自动机。（或者直接建立广义后缀自动机）
下面只要统计长度小于等于 n 的串即可。这可以从 parent 树即后缀树来考虑，注意到每个节点可以接收的子串长度为[mxlen[fa[x]]+1,mxlen[x]]
只要对这个长度区间对n取min再统计即可
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
int fa[],go[][],mx[],n,t,last;
char a[];
void add(int c)
{
int np,nq,q,p=last;
if (!go[last][c])
{
np=++t;
mx[np]=mx[p]+;
for (;p&&!go[p][c]; p=fa[p]) go[p][c]=np;
}
else np=;
if (!p) fa[np]=;
else {
q=go[p][c];
if (mx[q]==mx[p]+) fa[np]=q;
else {
nq=++t;
mx[nq]=mx[p]+;
memcpy(go[nq],go[q],sizeof(go[q]));
fa[nq]=fa[q]; fa[q]=fa[np]=nq;
for (;go[p][c]==q; p=fa[p]) go[p][c]=nq;
}
}
last=go[last][c];
} int main()
{
scanf("%d",&n);
scanf("%s",a+);
last=t=;
for (int i=; i<=n; i++)
add(a[i]-'a');
for (int i=; i<=n; i++)
add(a[i]-'a');
last=;
for (int i=n; i; i--)
add(a[i]-'a');
for (int i=n; i; i--)
add(a[i]-'a');
ll ans=;
for (int i=; i<=t; i++)
ans+=min(n,mx[i])-min(mx[fa[i]],n);
printf("%lld\n",ans);
}
自动机
另一种诡异的做法：由于数据随机，那么当串长足够大时很大概率都是互不相同的，干脆就直接认为全不相同
因此只要找小串长的不同种类即可，这就直接用 hash
暴力判断即可。
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
char a[];
set<ll> f[];
int n;
using namespace std;
typedef long long ll;
const int mx=;
int main()
{
scanf("%d",&n);
scanf("%s",a);
for (int i=; i<n; i++)
{
ll h1=,h2=;
for (int l=; l<min(n,mx); l++)
{
h1=h1*+a[(i+l)%n]-'a';
h2=h2*+a[(i-l+n)%n]-'a';
f[l].insert(h1);
f[l].insert(h2);
}
}
ll ans=2ll*n*max(,n-mx);
for (int l=; l<mx; l++)
ans+=f[l].size();
printf("%lld\n",ans);
}