多组数据,我把SA的那些数组清空,如果不清空rk和tp数组会RE或WA,为啥啊?
for(int i=1;i<=n;i++) rk[i] = a[i], tp[i] = i;
话说有这句话这两个数组不就覆盖了吗?
有没有大佬看看这份代码哪里会穿。
记录:都清空 不清空rk和tp
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define QWQ cout<<"QwQ"<<endl;
#define ll long long
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define OBGG for(int i=2;i<=N-1000;i++) ob[i] = ob[i>>1] + 1;
using namespace std;
const int N=51010;
const int qwq=303030;
const int inf=0x3f3f3f3f;
int T,n;
char s[N];
int d[N],g[N];
ll ans;
int ob[N];
inline int mi(int aa,int bb) { return aa<bb?aa:bb; }
struct SA{
int m;
int a[N];
int sa[N],rk[N],tp[N],c[N],h[N];
int f[N][20];
void chu() {
memset(sa,0,sizeof(sa));
memset(h,0,sizeof(h));
memset(tp,0,sizeof(tp));
memset(rk,0,sizeof(rk));
memset(a,0,sizeof(a));
}
void Qsort() {
for(int i=1;i<=n;i++) c[rk[i]]++;
for(int i=1;i<=m;i++) c[i] += c[i-1];
for(int i=n;i>=1;i--) sa[ c[rk[tp[i]]]-- ] = tp[i];
for(int i=1;i<=m;i++) c[i] = 0;
}
void built() {
m = 30;
for(int i=1;i<=n;i++) rk[i] = a[i], tp[i] = i;
Qsort();
for(int k=1; ; k<<=1) {
int p = 0;
for(int i=1;i<=k;i++) tp[++p] = n - k + i;
for(int i=1;i<=n;i++) if(sa[i] > k) tp[++p] = sa[i] - k;
Qsort();
swap(rk,tp);
rk[ sa[1] ] = p = 1;
for(int i=2;i<=n;i++) {
if(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+k]==tp[sa[i-1]+k])
rk[sa[i]] = p;
else
rk[sa[i]] = ++p;
}
m = p;
if(p==n) break;
}
for(int i=1,l=0,o; i<=n; h[rk[i++]]=l)
for(l=(l?l-1:0), o=sa[rk[i]-1]; a[i+l]==a[o+l]; ++l) ;
for(int i=1;i<=n;i++) f[i][0] = h[i];
for(int k=1;k<=17;k++)
for(int i=1;i+(1<<k)-1<=n;i++)
f[i][k] = mi(f[i][k-1],f[ i+(1<<k-1) ][k-1]);
}
inline int MIN(int i,int j) { int k = ob[j-i+1]; return mi(f[i][k],f[j-(1<<k)+1][k]); }
inline int lcp(int x,int y) {
x = rk[x]; y = rk[y];
if(x>y) swap(x,y);
return MIN(x+1,y);
}
} zheng,fan;
void qiu() {
for(int i=1;i<=n;i++) {
for(int j=2;j*i<=n;j++) {
int zl = (j-1) * i, zr = j * i;
int yl = (n-zl+1), yr = (n-zr+1);
int tongr = zheng.lcp(zl,zr), tongl = fan.lcp(yl,yr);
tongl = mi(tongl,i); tongr = mi(tongr,i);
if(tongl+tongr<=i) continue;
d[zr-tongl+i]++; d[zr+tongr]--;
g[zl-tongl+1]++; g[zl+tongr-i+1]--;
}
}
for(int i=1;i<=n;i++) d[i] += d[i-1], g[i] += g[i-1];
}
int main() {
OBGG
scanf("%d",&T);
while(T--) {
scanf("%s",s+1); n = strlen(s+1);
zheng.chu(); fan.chu();
for(int i=1;i<=n;i++)
zheng.a[i] = fan.a[n-i+1] = s[i] - 'a' + 1;
zheng.built(); fan.built();
memset(d,0,sizeof(d));
memset(g,0,sizeof(g));
ans = 0;
qiu();
for(int i=2;i<=n-2;i++) ans += d[i]*g[i+1];
cout<<ans<<"\n";
}
return 0;
}