以此纪念我都快忘了的后缀自动机（捂脸）
不过这题有两种做法：
用后缀自动机，先把原串再接遍中间加入特殊连接字符再把原串反接两遍，对这个新构造出的串做后缀自动机。（或者直接建立广义后缀自动机）
下面只要统计长度小于等于 n 的串即可。这可以从 parent 树即后缀树来考虑，注意到每个节点可以接收的子串长度为[mxlen[fa[x]]+1,mxlen[x]]
只要对这个长度区间对n取min再统计即可
1 #include2 3 using namespace std; 4 typedef long long ll; 5 int fa[400010],go[400010][26],mx[400010],n,t,last; 6 char a[50010]; 7 void add(int c) 8 { 9 int np,nq,q,p=last;10 if (!go[last][c])11 {12 np=++t;13 mx[np]=mx[p]+1;14 for (;p&&!go[p][c]; p=fa[p]) go[p][c]=np;15 }16 else np=0;17 if (!p) fa[np]=1;18 else {19 q=go[p][c];20 if (mx[q]==mx[p]+1) fa[np]=q;21 else {22 nq=++t;23 mx[nq]=mx[p]+1;24 memcpy(go[nq],go[q],sizeof(go[q]));25 fa[nq]=fa[q]; fa[q]=fa[np]=nq;26 for (;go[p][c]==q; p=fa[p]) go[p][c]=nq;27 }28 }29 last=go[last][c];30 }31 32 int main()33 {34 scanf("%d",&n);35 scanf("%s",a+1);36 last=t=1;37 for (int i=1; i<=n; i++)38 add(a[i]-'a');39 for (int i=1; i<=n; i++)40 add(a[i]-'a');41 last=1;42 for (int i=n; i; i--)43 add(a[i]-'a');44 for (int i=n; i; i--)45 add(a[i]-'a');46 ll ans=0;47 for (int i=2; i<=t; i++)48 ans+=min(n,mx[i])-min(mx[fa[i]],n);49 printf("%lld\n",ans);50 }
另一种诡异的做法：由于数据随机，那么当串长足够大时很大概率都是互不相同的，干脆就直接认为全不相同
因此只要找小串长的不同种类即可，这就直接用 hash
暴力判断即可。
1 #include2 3 using namespace std; 4 typedef long long ll; 5 char a[50010]; 6 set f[20]; 7 int n; 8 using namespace std; 9 typedef long long ll;10 const int mx=15;11 int main()12 {13 scanf("%d",&n);14 scanf("%s",a);15 for (int i=0; i