SA后缀数组模板

int n, m, ork[MAXN], rk[MAXN], sa[MAXN], cnt[MAXN], id[MAXN], h[MAXN];
string s;void SA() {m = 26;for(int i = 1; i <= n; ++i) {cnt[rk[i] = s[i] - 'a' + 1]++;}for(int i = 1; i <= m; ++i) {cnt[i] += cnt[i - 1];}for(int i = n; i >= 1; --i) {sa[cnt[rk[i]]--] = i;}for(int w = 1; ; w <<= 1) {int tot = 0;for(int i = n - w + 1; i <= n; ++i) {id[++tot] = i;}for(int i = 1; i <= n; ++i) {if(sa[i] > w) {id[++tot] = sa[i] - w;}}fill(cnt, cnt + m + 1, 0);for(int i = 1; i <= n; ++i) {cnt[rk[i]]++;}for(int i = 1; i <= m; ++i) {cnt[i] += cnt[i - 1];}for(int i = n; i >= 1; --i) {sa[cnt[rk[id[i]]]--] = id[i];}int p = 0;for(int i = 1; i <= n; ++i) {ork[i] = rk[i];}for(int i = 1; i <= n; ++i) {if(ork[sa[i]] == ork[sa[i - 1]] && ork[sa[i] + w] == ork[sa[i - 1] + w]) {rk[sa[i]] = p;}else {rk[sa[i]] = ++p;}}if(p == n) {break;}m = p;}
}void geth() {for(int i = 1, j = 0; i <= n; ++i) {if(!rk[i]) {continue;}for(j = max(0, j - 1); s[i + j] == s[sa[rk[i] - 1] + j]; ++j) {}h[rk[i]] = j;}
}