感觉端点的选取应该是轮换对称的？但是不对
by Cupids_Bow @ 2022-05-10 22:04:39
没过能不能看下代码（（
by w23c3c3 @ 2022-05-10 22:10:14
@[w23c3c3](/user/109942)
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=1e5+5;
int _=1;
struct SA{
int n,m;
char s[N];
int sa[N],rk[N],height[N],h[N];
int minn[N][21],lg[N];
void init(int _n,int _m){
n=_n;
m=_m;
}
void buildsa(){
static int x[N*2],y[N*2],c[N];
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n*2;i++) x[i]=y[i]=0;
for(int i=1;i<=n;i++) y[i]=0;
for(int i=1;i<=n;i++) c[x[i]=(s[i]-'a'+1)]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=1;
num=1;
for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num==n) break;
m=num;
}
for(int i=1;i<=n;i++) rk[sa[i]]=i;
}
void buildheight(){
int k=0;
for(int i=1;i<=n;i++){
if(rk[i]==1) continue;
if(k) --k;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
height[rk[i]]=k;
}
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) minn[i][0]=height[i];
for(int j=1;j<=20;j++)
for(int i=1;i+(1<<j)-1<=n;i++) minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
}
int get_lcp(int l,int r){
l=rk[l],r=rk[r];
if(l>r) swap(l,r);
l++;
int k=lg[r-l+1];
return min(minn[l][k],minn[r-(1<<k)+1][k]);
}
}sa1,sa2;
int n;
int f[N],g[N];
void work(){
cin>>sa1.s+1;
n=strlen(sa1.s+1);
for(int i=1;i<=n;i++) f[i]=g[i]=0;
sa1.init(n,26);
sa2.init(n,26);
for(int i=1;i<=n;i++) sa2.s[i]=sa1.s[n-i+1];
sa1.buildsa();
sa2.buildsa();
sa1.buildheight();
sa2.buildheight();
for(int len=1;len<=n/2;len++){
for(int i=len;i+len<=n;i+=len){
int l=i,r=i+len;
int L=n-(r-1)+1,R=n-(l-1)+1;
int lcp=min(len,sa1.get_lcp(l,r));
int lcs=min(len-1,sa2.get_lcp(L,R));
if(lcp+lcs>=len){
f[r+lcp-(lcp+lcs-len+1)]++;
f[r+lcp]--;
g[l-lcs]++;
g[l-lcs+(lcp+lcs-len+1)]--;
}
}
}
for(int i=1;i<=n;i++) f[i]+=f[i-1],g[i]+=g[i-1];
ll ans=0;
for(int i=2;i<=n;i++) ans+=1ll*f[i-1]*g[i];
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>_;
while(_--){
work();
}
return true&&false;
}
```
这份是AC的
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=1e5+5;
int _=1;
struct SA{
int n,m;
char s[N];
int sa[N],rk[N],height[N],h[N];
int minn[N][21],lg[N];
void init(int _n,int _m){
n=_n;
m=_m;
}
void buildsa(){
static int x[N*2],y[N*2],c[N];
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n*2;i++) x[i]=y[i]=0;
for(int i=1;i<=n;i++) y[i]=0;
for(int i=1;i<=n;i++) c[x[i]=(s[i]-'a'+1)]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=1;
num=1;
for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num==n) break;
m=num;
}
for(int i=1;i<=n;i++) rk[sa[i]]=i;
}
void buildheight(){
int k=0;
for(int i=1;i<=n;i++){
if(rk[i]==1) continue;
if(k) --k;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
height[rk[i]]=k;
}
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) minn[i][0]=height[i];
for(int j=1;j<=20;j++)
for(int i=1;i+(1<<j)-1<=n;i++) minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
}
int get_lcp(int l,int r){
l=rk[l],r=rk[r];
if(l>r) swap(l,r);
l++;
int k=lg[r-l+1];
return min(minn[l][k],minn[r-(1<<k)+1][k]);
}
}sa1,sa2;
int n;
int f[N],g[N];
void work(){
cin>>sa1.s+1;
n=strlen(sa1.s+1);
for(int i=1;i<=n;i++) f[i]=g[i]=0;
sa1.init(n,26);
sa2.init(n,26);
for(int i=1;i<=n;i++) sa2.s[i]=sa1.s[n-i+1];
sa1.buildsa();
sa2.buildsa();
sa1.buildheight();
sa2.buildheight();
for(int len=1;len<=n/2;len++){
for(int i=1;i+len<=n;i+=len){
int l=i,r=i+len;
int L=n-(r-1)+1,R=n-(l-1)+1;
int lcp=min(len,sa1.get_lcp(l,r));
int lcs=min(len-1,sa2.get_lcp(L,R));
if(lcp+lcs>=len){
f[r+lcp-(lcp+lcs-len+1)]++;
f[r+lcp]--;
g[l-lcs]++;
g[l-lcs+(lcp+lcs-len+1)]--;
}
}
}
for(int i=1;i<=n;i++) f[i]+=f[i-1],g[i]+=g[i-1];
ll ans=0;
for(int i=2;i<=n;i++) ans+=1ll*f[i-1]*g[i];
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>_;
while(_--){
work();
}
return true&&false;
}
```
这份是WA的
by Cupids_Bow @ 2022-05-10 22:13:47
@[Cupids_Bow](/user/96720) 我测出来你是因为 l-lcs<0 了。
by w23c3c3 @ 2022-05-10 22:24:27
@[w23c3c3](/user/109942)
嗷嗷，好像还是多组数据初始挂了，最后还是没注意到这个，感谢dalao/bx
by Cupids_Bow @ 2022-05-10 22:33:54
@[Cupids_Bow](/user/96720) 诶是不是因为 l=1 的时候， R 就 =0，然后在 getlcp 的时候会算一些奇怪东西（？
by w23c3c3 @ 2022-05-10 22:36:09
哦 R 是 n+1。
这样就会出现上次没清空然后引发求 rk[L],rk[R] 的最小值出问题。
by w23c3c3 @ 2022-05-10 22:38:05
@[w23c3c3](/user/109942)
刚刚初始化把rk清了就没问题了，（偷懒把人偷炸了
by Cupids_Bow @ 2022-05-10 22:41:29
想的是sa和rk会重新求一遍就只清了辅助数组
by Cupids_Bow @ 2022-05-10 22:42:29
/fad
by w23c3c3 @ 2022-05-10 22:43:06