后缀数组

后缀数组感觉有点不好解释，简单记录一下板子。

后缀数组性质

lcp(i, j):指的是第i个后缀以及第j个后缀的最大公共前缀的长度

• lcp(i, j) = lcp(j, i)

• lcp(i, i) = len(i)

• lcp(i, j) = min(lcp(i, k), lcp(k, j))

在o(nlogn)的时间复杂度内处理一个字符串，得到三个数组。

sa[i]：表示排名为i的后缀是字符串中第几个后缀。

rk[i]：表示字符串中第几个后缀的排名。

height[i]：sa[i] 与 sa[i - 1] 的后缀的最长公共前缀的长度。

int n, m;
int o[N];
int c[N], x[N], y[N], sa[N], rk[N], height[N];
char s[N];
// x：最开始表示每个字符离散化后的值，也就是Ascll码，第一关键值
void get_sa() {for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++; for(int i = 2; i <= m; i ++) c[i] += c[i - 1];for(int i = n; i; i --) sa[c[x[i]] --] = i; // 以上是得到按照第一个字符进行排序后的后缀顺序sa，以及x数组，也就是每个后缀的第一关键字 for(int k = 1; k <= n; k <<= 1) { int num = 0;for(int i = n - k + 1; i <= n; i ++) y[++ num] = i; // 没有第二关键字就是最小的直接排序就行 for(int i = 1; i <= n; i ++) if(sa[i] > k) // 当前大小排名为i的后缀存在第二关键字  y[++ num] = sa[i] - k; // 减k之后才是以当前为第二关键字的后缀// 以上是按照第二关键字进行排序得到排序后的后缀顺序y  for(int i = 1; i <= m; i ++) c[i] = 0;for(int i = 1; i <= n; i ++) c[x[i]] ++; for(int i = 2; i <= m; i ++) c[i] += c[i - 1];for(int i = n; i; i --) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0; // 以上是按照第一关键字进行排序之后的后缀顺序sa// 当前的操作已经完成，需要更新一下第一关键字，因为对于下一次循环的排序来说，第一关键字是当前的第一关键字和第二关键字的整体，所以需要对这个整体进行离散得到新的x数组第一关键字 swap(x, y); // y已经没用了，直接用来存储之前的第一关键字进行使用x[sa[1]] = 1, num = 1; // 第一个位置for(int i = 2; i <= n; i ++)  x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num; // 如果第一关键字和第二关键字都相同则num值等于上一个位置，否则加一，因为当前的sa顺序已经是排序之后的，只需要考虑相等值得离散值相同即可。if(num == n) break; // 排序完成m = num;// 更新一下值域范围，一个小的时间优化}
} void get_height() {for(int i = 1; i <= n; i ++) rk[sa[i]] = i;for(int i = 1, k = 0; i <= n; i ++) {if(rk[i] == 1) continue;if(k) k --; int j = sa[rk[i] - 1];while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;height[rk[i]] = k;} 
}inline void sovle() {cin >> s + 1;n = strlen(s + 1), m = 122;get_sa();get_height();for(int i = 1; i <= n; i ++) cout << sa[i] << " ";cout << endl;for(int i = 1; i <= n; i ++) cout << rk[i] << " ";cout << endl;for(int i = 1; i <= n; i ++) cout << height[i] << " ";cout << endl;
}