后缀数组-个人总结

## 间隔符号最好不相同！ ## 要深刻理解height数组的“字符串平移”含义 ## 一个常用的技巧：枚举串的长度len，每隔len个放一个观察点，总复杂度$O(N\log N)$ 看12月集训Day2. # 后缀数组 之前写过[一篇自认为特别棒的题解](https://www.luogu.org/blog/i207M/hou-zhui-shuo-zu-xue-xi-bi-ji)，觉得看那个就够了； 注意：桶的大小和n一定要区分清楚！ ### 证明h[i]>=h[i-1]-1 [from](https://www.cnblogs.com/victorique/p/8480093.html) ``` 首先我们不妨设第i-1个字符串按排名来的前面的那个字符串是第k个字符串，注意k不一定是i-2，因为第k个字符串是按字典序排名来的i-1前面那个，并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。 这时，依据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。 ``` ### [SDOI2016]生成魔咒 一个重要的性质：一个字符串本质不同的子串个数就是$n(n-1)/2-\sum h[i]$，减去h的过程就相当于是对每个后缀去掉重复的前缀。对于这道题，每次加入一个前缀，所以我们把字符串倒过来处理，变成每次加入一个后缀，**类似地，当前加入的后缀，重复的前缀个数，就是已经加入的后缀中，排名和i最接近的两个后缀，与它俩的lcp的max**。 ### POJ 1743 首先差分，之后一种做法是二分+哈希，但是我们在学习SA！ 构造出$height$，将$height[i]>=mid$的分成一组，如果一组内后缀位置的差的最大值$>mid$，那么有解。注意如果一个点的$height[i]>=mid$，那么一定别忘了加上它的前一个，然后维护minmax。 ### 求回文 设原串为S，将原串翻转后得到T，对于S+'~'+T跑一个SA，然后枚举每个回文重心，求与T中对称位置的lcp，就是回文。 ~~但是完全比不上$O(N)$的马拉车~~ ## HDU 3518 求出现多次的本质不同的子串个数，$O(N^2)$。 枚举子串长度len，然后扫描height，按len分为多组，看每组内最左最右端点的差是否>=len。 这道题是多组数据，所以有很多**清空的地方值得注意**： 1.**tp[n+1]**一定要清空！因为比较时为了防止越界，是和n+1取min的，这里默认n+1为0！ **准确的说，不只是tp[n+1]要清空，因为每次排序时会交换tp和rk，所以rk[n+1]也要清空！** 2.h[n+1]也要设为0，因为偷懒不想加一句特判，这就必须要保证h[n+1]为0。 ### [HAOI2016]找相同字符 $N^2$枚举起点的方法很好想，然后考虑优化：LCP为一段区间的H的最小值，所以有单调性，于是可以分治或者线段树+扫描线，但是还有更加优雅的方法：单调栈。 我们维护一个自顶向下递增的单调栈，我们枚举哪个串在前，考虑另一个串一个点的贡献，一定是后缀的最小值之和，于是我们可以用单调栈维护。画出图来就是：  于是每段的贡献就是$\sum \text{区间内合法的左端点数量}\times \min$ ### 多串的最长公共子串 中间插入~后跑SA，二分长度，分组，看组内是不是全部字符串都出现过。 ## 本质不同的字典序第k小 hdu5008 根据height数组，每个后缀的贡献的不同子串就是$n-sa[i]+1-h[i]$，按排名从小到大枚举后缀，求出前缀和，我们就可以通过二分找到第一个$sum[t]>=k$的位置，同时算出这个字符串的长度，但是！这并不一定是最优解，因为**要求左端点最靠前**，所以这个子串的左端点可能不是二分得到的t，而是排名在t之后，但是前缀依旧包含这个子串的，位置更靠前的后缀。 因为串已经确定了，我们就是要找到它出现的最早位置，我们可以二分r，使得$\min(h[t+1...r])>=len$，这些字符串依旧包含len这个前缀，于是我们就查询$\min(sa[t...r])$即可得出答案。具体实现使用两个ST表。 ### 品酒大会 之前一直说“按height分组”云云，其实就是合并相邻两个排名的字符串，而这种合并可以很方便的利用并查集维护相关信息。对于这道题，只需要维护size,max,min就可以了。**注意负负得正！** ## 优秀的差分 另一篇博客。