后缀数组的模板。这样说明就非常具体了吧！
/* * 后缀数组模板-倍增法 * 用法： * 1、读取字符串转换成int数组。长度为len。下标从0開始 * 2、在字符串末尾加一字典序最小字符，一般为0,并找到最大的字符设为maxa * 3、调用函数da(num,sa,len+1,maxa+1) * 求得的sa数组的含义： sa[i]为第i字典序后缀字符串的首字母下标 * 4、调用函数build_height(num,sa,len) * 求得的ranking数组的含义： ranking[i]为首字母下标为i的后缀数组的字典序的名次 * 求得的height数组含义： height[i]为第i字典序后缀与第i-1字典序后缀的最长公共前缀，height[1] = 0; * h[i]=height[rank[i]]。也就是suffix(i)和在它前一名的后缀的最长公共前缀。* 注意事项： * 转化为数字的字符串最小数值必须不小于1。假设是0的话会Runtime Error，请自重....... */ #include <iostream> #include <algorithm> #include <cstdio> #define INF 2*0x3f3f3f3f using namespace std; const int maxn = 200001; //注意数组的大小。记得更改 int wa[maxn], wb[maxn], wv[maxn], wss[maxn]; int cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a + l] == r[b + l]; } void da(int *r, int *sa, int n, int m) { //r为所求取的转化字符串 sa为求得的sa数组 n为数组长度+1 m为数组的最大值+1 int i, j, p, *x = wa, *y = wb, *t; for (i = 0; i < m; i++) wss[i] = 0; for (i = 0; i < n; i++) wss[x[i] = r[i]]++; for (i = 1; i < m; i++) wss[i] += wss[i - 1]; for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i; for (j = 1, p = 1; p < n; j *= 2, m = p) { for (p = 0, i = n - j; i < n; i++) y[p++] = i; for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j; for (i = 0; i < n; i++) wv[i] = x[y[i]]; for (i = 0; i < m; i++) wss[i] = 0; for (i = 0; i < n; i++) wss[wv[i]]++; for (i = 1; i < m; i++) wss[i] += wss[i - 1]; for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i]; for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++) x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ?
p - 1 : p++; } return; } int ranking[maxn], height[maxn]; void build_height(int *r, int *sa, int n) { //r为求得的转化原始数组，sa为已经求得的数组。n为len int i, j, k = 0; for (i = 1; i <= n; i++) ranking[sa[i]] = i; for (i = 0; i < n; height[ranking[i++]] = k) { for (k ? k-- : 0, j = sa[ranking[i] - 1]; r[i + k] == r[j + k]; k++); } } int sa[maxn], r[maxn]; int main() { freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); return 0; }
转载于:https://www.cnblogs.com/brucemengbm/p/7225753.html
相关资源：数据结构—成绩单生成器