# 后缀数组模板

namespace SA{
#define _next(_x) (_x+1)
#define _check (y[sa[i]]!=y[sa[i-1]] || y[nxt[sa[i]]]!=y[nxt[sa[i-1]]])
int nxt[MAXN], _nxt[MAXN];
int x[MAXN], y[MAXN], c[MAXN], t[MAXN];
int ranks[MAXN], sa[MAXN];
int height[MAXN];
int n, m;
bool flag;
char *s;
inline int gainNext(int x){
if(!x) return 0;
return _next(x)>n?0:_next(x);
}
void init(char *_s, int _n, int _m){
s = _s;
n = _n;
m = _m;
flag = true;
}
void calc_height(){
for(int i = 1; i <= n; i++) ranks[sa[i]] = i;
for(int i = 1; i <= n; i++){
if(ranks[i]==1) continue;
int len = max(0, height[ranks[i-1]]-1);
int j = sa[ranks[i]-1];
while(i+len-1<n&&j+len-1<n&&s[i+len-1]==s[j+len-1]) len++;
height[ranks[i]] = len;
}
}
void solve(char *_s, int _n, int _m = 128){
init(_s, _n, _m);
for(int i = 1; i <= n; i++) nxt[i] = gainNext(i);
for(int i = 1; i <= n; i++) x[i] = s[i];
for(int i = 1; i <= n; i++) y[i] = i;
//first sort
for(int i = 0; i <= m; i++) c[i] = 0;
for(int i = 1; i <= n; i++) c[x[i]]++;
for(int i = 1; i <= m; i++) c[i] += c[i-1];
for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
for(int k = 1; k <= n && flag; k<<=1){
// keywords2(seg2)
for(int i = 1; i <= n; i++) ranks[sa[i]] = i;
for(int i = 1; i <= n; i++) t[i] = ranks[nxt[i]];
for(int i = 0; i <= n; i++) c[i] = 0;
for(int i = 1; i <= n; i++) c[t[i]]++;
for(int i = 1; i <= n; i++) c[i] += c[i-1];
for(int i = n; i >= 1; i--) sa[c[t[i]]--] = i;
for(int i = 1; i <= n; i++) y[i] = sa[i];
// (log(k)+2)th sort
for(int i = 0; i <= m; i++) c[i] = 0;
for(int i = 1; i <= n; i++) c[x[i]]++;
for(int i = 1; i <= m; i++) c[i] += c[i-1];
for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
int cnt = 0;    swap(x, y); // y->x throw,x->y save
for(int i = 1; i <= n; i++) x[sa[i]] = _check?++cnt:cnt;
cnt>=n?flag=false:m=cnt;
swap(nxt, _nxt);
for(int i = 1; i <= n; i++) nxt[i] = _nxt[_nxt[i]];
}
// Output();
for(int i = 1; i <= n; i++) ranks[sa[i]] = i;
}
void Output(){
static int len = 1;
printf("========== len: %d ==========\n", len);
for (int i = 1; i <= n; i++)
{
int now = sa[i];
for (int j = 1; j <= n; j++)
{
printf("%c", now ? s[now - 1] : ' ');
// printf("%d ", now);
now = gainNext(now);
}
printf("\n");
}
printf("=============================\n", len);
len *= 2;
}
void Output_(){
static int len = 1;
printf("========== len: %d ==========\n", len);
for (int i = 1; i <= n; i++)
{
printf("%d%c", nxt[i], i == n ? '\n' : ' ');
}
printf("=============================\n", len);
len *= 2;
}
}

(=￣ω￣=)··· 暂无内容！

10

0

2

1