后缀数组
定义： 后缀就是从字符串的某个位置i到字符串末尾的子串，我们定义以s的第i个字符为第一个元素的后缀为\(suff(i)\)
辅助数组：
\(sa_i\)：表示排名为\(i\)的后缀的起始位置的下标
\(rk_i\)：表示起始位置的下标为\(i\)的后缀的排名
\(x_i\)：表示起始位置的下标为\(i\)的后缀的第一关键字
\(y_i\)：表示起始位置的下标为\(i\)的后缀的第二关键字
后缀数组的思想：
先说最暴力的情况，快排\(O(nlogn)\)每个后缀，但是这是字符串，所以比较任意两个后缀的复杂度其实是\(O(n)\)，这样一来就是接近\(O(n^2logn)\)的复杂度，数据大了肯定是不行的，所以我们这里有两个优化。
倍增： 每次以前\(2^k\)为第一关键字，后\(2^k\)为第二关键字（没有的补零）进行合并，预处理出按第一个字符排序的情况，当最后每个后缀的排名都不同时，排序完成
基数排序： 简单来说，就是个桶
代码具体流程：
- 按第一个字符排序
for (register int i = 1;i <= n;i++) ++c[x[i] = s[i]];
for (register int i = 1;i <= m;i++) c[i] += c[i-1];
for (register int i = n;i >= 1;i--) sa[c[x[i]]--] = i;
举个例子：
\[abbac \]-
第一个循环结束后，\(c\)数组的情况是2 2 1
-
第二个循环结束后，\(c\)数组的情况是2 4 5
-
第三个循环从后往前循环，使相同字符排在后面的依旧排在后面，得到的\(sa\)数组为0 2 3 1 4
- 按第二关键字的排名求y
-
最后的n-k+1~n部分没有第二关键字，排在最前面
-
枚举串的排名，如果排名为\(i\)的串可以作为第二关键字，就入队，排名在前的先入后出
int num = 0;
for (register int i = n-k+1;i <= n;i++) y[++num] = i;
for (register int i = 1;i <= n;i++) if (sa[i] > k) y[++num] = sa[i]-k;
- 求解sa
因为\(y\)数组已经是排好序的，基数排序又是按照\(x\)排好序的，所以正常进行排序就好
memset(c,0,sizeof(c));
for (register int i = 1;i <= n;i++) ++c[x[i]];
for (register int i = 1;i <= m;i++) c[i] += c[i-1];
for (register int i = n;i >= 1;i--) sa[c[x[y[i]]]--] = y[i],y[i] = 0;
- 更新x
根据更新好的\(sa\)，如果第一第二关键字相同，排名相同，否则就顺序排
x[sa[1]] = 1,num = 1;
for (register 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;
最长公共前缀
定义： \(LCP(i,j)\)为\(suff(sa_i)\)与\(suff(sa_j)\)的最长公共前缀
性质：
-
\(LCP(i,j) \text{=} LCP(j,i)\)
-
\(LCP(i,i) \text{=} len(sa_i) \text{=} n \text{-} sa_i \text{+} 1\)
-
\(LCP(i,k) \text{=} min(LCP(i,j),LCP(j,k))\)，其中\(1\leq i\leq j\leq k\leq n\)
-
\(LCP(i,k) \text{=} min(LCP(j,j-1))\)，其中\(i<j\leq k\)
前两条性质的正确性应该不难想吧，最主要的就是第三条，第四条根据第三条也不难想，下面给出证明：
设\(LCP(i,k) \text{=} q,p \text{=} min(LCP(i,j),LCP(j,k)),u \text{=} stuff(sa_i),v \text{=} stuff(sa_j),w = stuff(sa_k)\)
不难想到\(q \geq p\)，如果假设\(q > p\)，则有\(u_{p+1} \neq v_{p+1}\)和\(v_{p+1} \neq w_{p+1}\)至少一条满足，且\(u_{p+1} = w_{p+1}\)
但是别忘了现在的\(u,v,w\)三者是有顺序关系的，则\(u_{p+1} \leq v_{p+1} \leq w_{p+1}\)，等号不同时成立，与上述\(u_{p+1} = w_{p+1}\)矛盾
假设假了，得出\(q \leq p\)，所以\(q = p\)
求解LCP：
设\(height_i\)为\(LCP(i,i-1)\)，则\(LCP(i,k)\text{=}min(height_j)\)，那么如何求解height???
因为下面嵌套的东西太多了，所以就不用LaTeX了，复制粘贴了
设h[i]=height[rk[i]]，同样的，height[i]=h[sa[i]];
首先我们不妨设第i-1个字符串按排名来的前面的那个字符串是第k个字符串
这时，依据height的定义，第k个字符串和第i-1个字符串的公共前缀自然是height[rk[i-1]]，现在先讨论一下第k+1个字符串和第i个字符串的关系。
第一种情况，第k个字符串和第i-1个字符串的首字符不同，那么第k+1个字符串的排名既可能在i的前面，也可能在i的后面，但没有关系，因为height[rk[i-1]]就是0了呀，那么无论height[rk[i]]是多少都会有height[rk[i]]>=height[rk[i-1]]-1，也就是h[i]>=h[i-1]-1。
第二种情况，第k个字符串和第i-1个字符串的首字符相同，那么由于第k+1个字符串就是第k个字符串去掉首字符得到的，第i个字符串也是第i-1个字符串去掉首字符得到的，那么显然第k+1个字符串要排在第i个字符串前面。同时，第k个字符串和第i-1个字符串的最长公共前缀是height[rk[i-1]]，
那么自然第k+1个字符串和第i个字符串的最长公共前缀就是height[rk[i-1]]-1。
到此为止，第二种情况的证明还没有完，我们可以试想一下，对于比第i个字符串的排名更靠前的那些字符串，谁和第i个字符串的相似度最高（这里说的相似度是指最长公共前缀的长度）？显然是排名紧邻第i个字符串的那个字符串了呀，即sa[rank[i]-1]。但是我们前面求得，有一个排在i前面的字符串k+1，LCP(rk[i],rk[k+1])=height[rk[i-1]]-1;
又因为height[rk[i]]=LCP(i,i-1)>=LCP(i,k+1)
所以height[rk[i]]>=height[rk[i-1]]-1，也即h[i]>=h[i-1]-1。
完整代码：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;
int n,m;
char s[maxn];
int sa[maxn],rk[maxn],x[maxn],y[maxn],c[maxn],height[maxn];
inline void getsa(){
// 第一次排序
for (register int i = 1;i <= n;i++) ++c[x[i] = s[i]];
for (register int i = 1;i <= m;i++) c[i] += c[i-1];
for (register int i = n;i >= 1;i--) sa[c[x[i]]--] = i;
for (register int k = 1;k <= n;k <<= 1){
int num = 0;
for (register int i = n-k+1;i <= n;i++) y[++num] = i;
for (register int i = 1;i <= n;i++) if (sa[i] > k) y[++num] = sa[i]-k;
memset(c,0,sizeof(c));
for (register int i = 1;i <= n;i++) ++c[x[i]];
for (register int i = 1;i <= m;i++) c[i] += c[i-1];
for (register int i = n;i >= 1;i--) sa[c[x[y[i]]]--] = y[i],y[i] = 0;
swap(x,y);
x[sa[1]] = 1,num = 1;
for (register 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;
if (num == n) break;
m = num;
}
for (int i = 1;i <= n;i++) rk[sa[i]] = i;
for (register int i = 1;i <= n;i++) printf("%d ",sa[i]);
}
void gethigh(){
int k = 0;
for (int i = 1;i <= n;i++){
if (rk[i] == 1) continue;
if (k) --k;
int j = sa[rk[i]-1];
while (j+k <= n&&i+k <= n&&s[i+k] == s[j+k]) ++k;
height[rk[i]] = k;
}
for (int i = 1;i <= n;i++) printf("%d ",height[i]);
}
int main(){
scanf ("%s",s+1);
n = strlen(s+1),m = 122;
getsa();gethigh();
return 0;
}
LCP的应用
- 求本质不同的子串个数
因为子串一定是后缀的前缀，我们用所有的子串个数，减掉重复的前缀即可。所有子串个数为\(\dfrac{n(n+1)}{2}\) ,重复的前缀个数为\(\sum\limits_{i=1}^{n}height_i\),其实就是按从小到大枚举后缀，减去这个后缀和前面一个重复的前缀,这样子做是对的是因为\(lcp(i,i-1)\)一定是\(lcp(j,i)\ (1\leq j<i)\)里面最大的。
- 求至少出现k次的子串最大长度
最后要求的子串一定是\(k\)个后缀的lcp。然后贪心地想，要让这个lcp最大，这\(k\)个后缀一定是连续的（指字典序）。然后我们现在就是求\([i,i+k-1]\)的所有后缀的lcp，这个其实就是\(lcp(i,i+k-1)\)，又等价于\(min(height_j)\ i<j\leq i+k-1\)。用个单调队列就可以了。
- 是否有子串不重叠地出现了至少两次
二分子串长度\(|s|\)，然后对每个i，求出最大的j，使得\(lcp(i,j)\ge s\)。然后用\(RMQ\) 查询\([i,j]\)的最大下标和最小下标，判断一下即可,总复杂度还是\(O(nlogn)\)的。