rk 排名，相同的排名相同
sa 排名的位置， 如果相同按位置顺序
y 辅助第二关键字
c 桶
理解
Q:为什么不可以将rk相同的按位置顺序变成不同的
A:这样如果第一关键字相同时比较第二关键字答案相反，就会有问题，如果这样对的，你的字典序在一开始就排好了
Q:y[sa[i]+k]不会越界吗？
A:如果越界前面的sa肯定会不同，因为长度不同，极限只有在最后一位会刚好多出一位，所以要多清一位
有些东西还是应该理解的深刻一点，而不是一味的学习，一味的赶进度
关于Height
把第i个串嵌到第i - 1个串去思考，然后就会发现存在另一个串与他相近，然后就让目标串夹在中间
证得 Height[i] >= Height[i - 1] - 1
#include<bits/stdc++.h>
#define rep(x, L, R) for(int x = (L), _x = (R); x <= _x; x++)
#define per(x, R, L) for(int x = (R), _x = (L); x >= _x; x--)
#define forgp(u, g, v) for(int iu = 0, v; iu < (int)g[u].size() && (v = g[u][iu], 1); iu++)
#define mp make_pair
#define siz(v) (int)(v).size()
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef double db;
const int N = 1e6 + 10;
int n;
char s[N];
int heg[N];
int sa[N], rk[N], c[N], y[N], m;
void SA(char *s, int n) {
m = 256;
rep(i, 1, n) {
c[rk[i] = s[i]]++;
}
rep(i, 1, m) c[i] += c[i - 1];
per(i, n, 1) {
sa[c[rk[i]]--] = i;
}
for(int k = 1; k < n; k <<= 1) {
int p = 0;
rep(i, n - k + 1, n) y[++p] = i;
rep(i, 1, n) if(sa[i] - k > 0) y[++p] = sa[i] - k;
rep(i, 0, m) c[i] = 0;
rep(i, 1, n) c[rk[y[i]]]++;
rep(i, 1, m) c[i] += c[i - 1];
per(i, n, 1) sa[c[rk[y[i]]]--] = y[i];
p = 0;
swap(rk, y);
rk[sa[1]] = ++p;
rep(i, 2, n) {
rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
}
m = p;
if(m >= n) break;
}
return;
}
void Heg(int n) {
rep(i, 1, n) heg[i] = 0;
rep(i, 1, n) {
if(rk[i] == 1) continue;
int p = sa[rk[i] - 1];
int k = max(0, h[a[i - 1]] - 1);
while(i + k <= n && p + k <= n && s[i + k] == s[p + k]) k++;
heg[rk[i]] = k;
}
return;
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
return 0;
}
题目
#include<bits/stdc++.h>
using namespace std;
const int N=31000;
const int Log=15;
char ch[N];
int T,n;
int l2[N];
int p2[Log+5];
int f[N],g[N];
struct SA
{
int n;
char ch[N];
int a[N],t[N],sa[N],c[N],m;
int h[N];
int st[Log+5][N];
void getst()
{
for(int i=1;i<=n;i++) st[0][i]=h[i];
for(int i=1;i<=Log;i++)
for(int j=1;j+p2[i]-1<=n;j++)
st[i][j]=min(st[i-1][j],st[i-1][j+p2[i-1]]);
return;
}
int LCP(int l,int r)
{
l=a[l],r=a[r];
if(l>r) swap(l,r);
l++;
int len=r-l+1;
len=l2[len];
return min(st[len][l],st[len][r-p2[len]+1]);
}
void getsa()
{
m=256;
for(int i=0;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[a[i]=ch[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[a[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(int i=n-k+1;i<=n;i++) t[++p]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) t[++p]=sa[i]-k;
for(int i=0;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[a[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[a[t[i]]]--]=t[i];
swap(a,t),p=1,a[sa[1]]=1;
for(int i=2;i<=n;i++) a[sa[i]]=(t[sa[i]]==t[sa[i-1]]&&sa[i]+k<=n&&sa[i-1]+k<=n&&t[sa[i]+k]==t[sa[i-1]+k])?p:++p;
if(p>=n) break;
m=p;
}
return;
}
void geth()
{
for(int i=0;i<=n;i++) h[i]=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1) continue;
int x=sa[a[i]-1];
int k=max(0,h[a[i-1]]-1);
while(max(i,x)+k<=n&&ch[i+k]==ch[x+k]) k++;
h[a[i]]=k;
}
return;
}
void Init(char *s)
{
n=strlen(s+1);
for(int i=1;i<=n;i++) ch[i]=s[i];
ch[n+1]=' ';
getsa();
geth();
getst();
return;
}
};
SA suf,pre;
int S(int x)
{
return x;
}
int P(int x)
{
return n+1-x;
}
void tag(int l,int r,int *s)
{
if(l<1) l=1;
if(r>n) r=n;
if(l>r) return;
s[l]++,s[r+1]--;
return;
}
long long sol()
{
for(int i=0;i<=n+1;i++) f[i]=0,g[i]=0;
for(int len=1;len<=n;len++)
{
for(int i=len;i+len<=n;i+=len)
{
int l=i+1,r=i+len;
int su=suf.LCP(S(i),S(i+len)),pr=pre.LCP(P(i),P(i+len));
l=max(l,i+len-pr+1);
r=min(r,i+su);
// cout<<i<<" "<<len<<" "<<su<<" "<<pr<<" "<<l<<" "<<r<<endl;
tag(l-len,r-len,g);
tag(l+len-1,r+len-1,f);
}
}
long long ans=0;
for(int i=1;i<=n;i++) f[i]+=f[i-1],g[i]+=g[i-1];
// for(int i=1;i<=n;i++) cout<<f[i]<<" "<<g[i]<<endl;
for(int i=2;i<=n;i++) ans+=f[i-1]*g[i];
return ans;
}
int main()
{
p2[0]=1;
for(int i=1;i<=Log;i++) p2[i]=p2[i-1]<<1;
l2[0]=-1;
for(int i=1;i<=3e4;i++) l2[i]=l2[i/2]+1;
scanf("%d",&T);
for(int am=1;am<=T;am++)
{
scanf("%s",ch+1);
n=strlen(ch+1);
suf.Init(ch);
reverse(ch+1,ch+n+1);
pre.Init(ch);
printf("%lld
",sol());
}
return 0;
}