后缀数组-学习笔记
i207M
2018-07-17 22:07:00
## 后缀数组
了解一发变量：
SA:排名为i的后缀的位置
rk:位置为i的后缀的排名
tp:第二关键字的排名为i的后缀的位置，还被用作rank的暂存
tax:每个排名对应的后缀数量
后缀数组就是为了求出sa和rk；
有意思的性质：
$rk[sa[i]]=i$还有$sa[rk[i]]=i$；
## 怎么求？
倍增＋基数排序；
何为倍增？先计算每个点开始向后$2^k$个字符的排名，两两拼接，算出$2^{k+1}$个字符的排名，直到区分出所有后缀；
我们已经有了用于排序的二元组，如何快速排序？介于每个数字最大不超过N，我们可以使用进阶桶排：基数排序；
（PS：正宗的基数排序时间复杂度为$O(n\log(Maxn))$）
## 注意
基排求前缀和要循环到M；
## 模板题代码与注释详解
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
#define pb push_back
#define gc getchar
template<class T>void in(T &x)
{
x = 0; bool f = 0; char c = gc();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
if (f) x = -x;
}
#undef gc
#define N 1000010
char s[N];
int n, m;
// 字符串长度，桶的大小
int sa[N], rk[N];
// SA:排名为i的后缀的位置
// rank:位置为i的后缀的排名
int tp[N], tax[N];
// tp:第二关键字的排名为i的后缀的位置，
// 还被用作rank的暂存
// tax:每个排名对应的后缀数量，用作桶
void rsort() { // 基数排序
for (ri i = 1; i <= m; ++i) tax[i] = 0;
for (ri i = 1; i <= n; ++i) ++tax[rk[i]];
// 第i个桶的内容：第一关键字为第i的数量
// 我们枚举每个位置的第一关键字排名（rk[i]），添加到桶中
for (ri i = 1; i <= m; ++i) tax[i] += tax[i - 1];
// 为了计算方便，我们求出前缀和
// 注意这里是循环到M
for (ri i = n; i >= 1; --i) sa[tax[rk[tp[i]]]--] = tp[i];
// 解释一下：因为第一关键字可能对应很多第二关键字
// 我们要在第一关键字相同的情况下排第二关键字
// 为了方便，我们倒序枚举所有的第二关键字，这样它一定是所在桶的最后一名
// 根据我们就求出的前缀和，它就是所有后缀的第tax[rk[tp[i]]]名
// （（第二关键字排名为i的后缀的位置）的桶编号）的前缀和排名
// 因为我们取出了一个元素，所以这个桶的size要-1
// 这样，这个排名的后缀的位置就是tp[i]
}
void ssort() {
for (ri i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i;
// 初始时，每个字符的排名就是ASCII码
// 第二关键字就随便给个i
rsort();
// 计算出长度为1的SA和rk
for (ri w = 1, p = 0; p < n && w <= n; m = p, w <<= 1) {
// m = p : 改变桶的大小为排名的数量，当数量为N时，完成区分排名
// w是要求出的后缀的长度
p = 0; // p是计数器，记录有多少个后缀的排名不同
for (ri i = n - w + 1; i <= n; ++i) tp[++p] = i;
// 对于起始位置在[n-w+1,n]的后缀，它们没有第二关键字，所以他们的第二关键字最小
for (ri i = 1; i <= n; ++i)
if (sa[i] > w) tp[++p] = sa[i] - w;
// IMPORTANT
// 枚举每一个排名，看看它距离字符串开头是否>w，这样，这个位置就是一个后缀的第二关键字
// 因为我们要在每一个后缀前接上长度为w的后缀，所以tp[++p] = sa[i] - w;
// 注意，编号越小表示这个后缀的起始位置越靠前
// 我们的第二关键字要从小到大，而我们正好是按照从小到大的顺序枚举每一个后缀
rsort(); // 再来一遍
swap(rk, tp); // WARN swap rank & tp
// 我们已经更新了SA，我们还要更新rk，此时tp已经无用，直接备份上一个rk
rk[sa[1]] = p = 1; // 排名第一的后缀直接加入
for (ri i = 2; i <= n; ++i)
rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w])
? p : ++p;
// 这里的条件是指：它的第一关键字和第二关键字是否都和前一个相同，如果是，它和上一个并列
// 如果不是，它的排名要+1
// 检查一下p==n，break;（我们已经区分出所有后缀）
}
}
signed main() {
scanf("%s", s + 1);
n = strlen(s + 1);
m = 127; // 初始桶的大小，因为char最大就是127
ssort();
for (ri i = 1; i <= n; ++i) printf("%d ", sa[i]);
return 0;
}
```
## 扩展
$lcp(x,y)$：字符串x与字符串y的最长公共前缀，在这里**指x号后缀与与y号后缀的最长公共前缀**；
$height[i]=lcp$($sa[i],sa[i$ - $1]$)，即排名为i的后缀与排名为i−1的后缀的最长公共前缀；
H[i]：height[rak[i]]，即i号后缀与它前一名的后缀的最长公共前缀；
重要性质：$H[i] \geqslant H[i - 1] - 1$；
通过这个我们可以快速求出$H[i]$，$k-1$后一位位匹配即可；
求出$height[i]$：
```
void geth() {
int j, k = 0;
for (ri i = 1; i <= n; ++i) {
if (k) --k;
j = sa[rk[i] - 1];
while (s[i + k] == s[j + k]) ++k;
h[rk[i]] = k;
}
}
```
关于LCP的几条性质
显而易见的
$LCP(i,j)=LCP(j,i)$；
$LCP(i,i)=len(sa[i])=n-sa[i]+1$；
**求解的重要性质：**
$LCP(i,k)=min(height[j])$
对于$i+1<=j<=k$；
## 给定字符串 S，求它所有本质不同的子串个数
### 区间？
给定一个字符串，每次询问区间$[l,r]$内本质不同的子串个数；
### HDU4622 代码
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
#define pb push_back
#define gc getchar
template<class T>void in(T &x)
{
x = 0; bool f = 0; char c = gc();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
if (f) x = -x;
}
#undef gc
#define N 2010
char s[N];
int n, m;
// 字符串长度，桶的大小
int sa[N], rk[N];
// SA:排名为i的后缀的位置
// rank:位置为i的后缀的排名
int tp[N], tax[N];
// tp:第二关键字的排名为i的后缀的位置，
// 还被用作rank的暂存
// tax:每个排名对应的后缀数量，用作桶
void rsort() { // 基数排序
for (ri i = 0; i <= m; ++i) tax[i] = 0;
for (ri i = 1; i <= n; ++i) ++tax[rk[i]];
for (ri i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (ri i = n; i >= 1; --i) sa[tax[rk[tp[i]]]--] = tp[i];
}
void ssort() {
for (ri i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i;
rsort();
for (ri w = 1, p = 0; p < n && w <= n; m = p, w <<= 1) {
p = 0;
for (ri i = n - w + 1; i <= n; ++i) tp[++p] = i;
for (ri i = 1; i <= n; ++i)
if (sa[i] > w) tp[++p] = sa[i] - w;
rsort();
swap(rk, tp);
rk[sa[1]] = p = 1;
for (ri i = 2; i <= n; ++i)
rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w])
? p : ++p;
}
}
int h[N];
void geth() {
int j, k = 0;
for (ri i = 1; i <= n; ++i) {
if (k) --k;
j = sa[rk[i] - 1];
while (s[i + k] == s[j + k]) ++k;
h[rk[i]] = k;
}
}
int st[N][12];
void init() {
// mem1(st);
for (ri i = 1; i <= n; ++i)st[i][0] = h[i];
for (ri j = 1; (1 << j) <= n; ++j) {
for (ri i = 1; i + (1 << j) - 1 <= n; ++i) {
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
il int qmin(int l, int r) { // 纯ST表模板，求[l,r]最小值
int k = 0, len = r - l + 1;
while ((1 << (k + 1)) <= len) ++k;
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
il int lcp(int l, int r) { // 利用数组H的性质，求出排名为l的后缀与排名为r的后缀的最长公共前缀
if (l > r) swap(l, r); // 很重要，根据算法，l，r大小不确定
return qmin(l + 1, r); // 排名l，r的后缀的最长公共前缀为min(h[l+1~j])
}
il int query(int l, int r) {
vector<int>pos;
for (ri i = 1; i <= n; ++i)
if (l <= sa[i] && sa[i] <= r) pos.pb(sa[i]); // pos存放在[l,r]之间的后缀
int sum = r - pos[0] + 1, tmp = sum; // sum为答案
// tmp：上一个字符串与之前所有字符串的最长公共前缀长度
for (ri i = 1; i < pos.size(); ++i) {
int k = lcp(rk[pos[i]], rk[pos[i - 1]]), len = r - pos[i] + 1;
// k：当前字符串与上一个字符串的最长公共前缀
tmp = min(tmp, k);
// 如果k<tmp，下一个tmp一定为k
tmp = max(tmp, min(k, r - pos[i - 1] + 1));
// 如果k>tmp，下一个tmp可能会为k，但是不能超过上一个后缀的区间长度，不然不符合规定
sum += len - min(tmp, len);
// 答案加上当前后缀的不同的前缀
}
return sum;
}
int t, q, l, r;
signed main() {
in(t);
while (t--) {
scanf("%s", s + 1);
n = strlen(s + 1);
m = 127;
ssort();
geth(); // GET Height
init(); // init ST
in(q);
while (q--) {
in(l), in(r);
printf("%d\n", query(l, r));
}
}
return 0;
}
```