终于正式开新算法啦！
发现学过的东西至今只会打板子很方赶紧学点很酷很炫的新算法安抚一下自己QAQ
前言（瞎扯）
后缀很好理解，就是一个字符串从某个位置到结尾连成的子串。
后缀数组（$Suffix\ Array$）就是把这些后缀按字典序排序后的数组。功能十分强大。
后缀数组主要是用来练习单调栈、二分和$ST$表的（雾
抄袭来源
http://www.cnblogs.com/zwfymqz/p/8413523.html
https://blog.csdn.net/a1035719430/article/details/80217267
https://www.cnblogs.com/victorique/p/8480093.html
#define
基本
$S(i)$：从位置$i$开始的后缀
$s[l,r]$：截取字符串$s$第$l$到第$r$个字符得到的子串
$n$：字符串长度
$len(p)$：字符串$p$的长度
后缀数组
$sa[i]$：（字典序）排第$i$名的后缀的下标
$rk[i]$：$S(i)$的排名
（显然$rk[sa[i]]=i$，$sa[rk[i]]=i$，知道一个就能求出另一个）
基数排序
$tax[i]$：第一关键字的桶（在基数排序中会处理成前缀和）
$tp[i]$：第二关键字排名第$i$名的下标
$m$：第一关键字有多少种排名（一开始为字符集大小）
height数组
$LCP(i,j)$：$S(i)$和$S(j)$的最长公共前缀
$lcp(i,j)$：$LCP(sa[i],sa[j])$（注意区分$LCP$）
$height[i]$：$lcp(i-1,i)$
$h[i]$：$height[rk[i]]$
后缀排序
先不管后缀数组干啥，得先能造出来后缀数组，就要对后缀排序。
$sort$显然不行。
于是有了倍增$O(n\log n)$、$DC3\ O(n)$、$SA-IS\ O(n)$、潮爷几个数组随便模拟$O(1)$的后缀排序。
不要学很酷很炫的算法，学了你就失败。——某金牌教练
所以我就学了最好懂(?)最好写(?)的倍增。
倍增
前置芝士
- 基数排序：
说实话现在还没搞懂。概括一下就是逐位比较，先比较个位，再比较十位。。。复杂度$O(n\lg n)$。不过在后缀排序中只有两个关键字，所以复杂度是$O(n)$的。
原理
$S(i)$的前$k$位就是$S(i-k)$的$k+1\sim 2k$位，两者的字典序排名也是一样的。那么我们就可以通过$S(i)$的前$k$位排名获取$S(i-k)$的$k+1\sim 2k$位的排名了。
设倍增跳到了第$k$层，我们要以每个后缀前$k$位的排名为第一关键字，$k+1\sim 2k$位的排名为第二关键字排序。结合上面那个原理转移，进行双关键字基数排序。
最多跳$\log n$层，每次基数排序是$O(n)$的，总复杂度$O(n\log n)$。
实现
int tax[maxn],tp[maxn],sa[maxn],rk[maxn],m,n;
char s[maxn];
void rsort(){
for(register int i=0;i<=m;++i)tax[i]=0;
for(register int i=1;i<=n;++i)++tax[rk[i]];
for(register int i=1;i<=m;++i)tax[i]+=tax[i-1];
for(register int i=n;i;--i)sa[tax[rk[tp[i]]]--]=tp[i];
}//基数排序
void ssort(){
m=75;
for(register int i=1;i<=n;++i)rk[i]=s[i]-'0',tp[i]=i;
rsort();
for(register int k=1,p=0;p<n;m=p,k<<=1){
p=0;
for(register int i=1;i<=k;++i)tp[++p]=n-k+i;
for(register int i=1;i<=n;++i)
if(sa[i]>k)tp[++p]=sa[i]-k;
rsort();
for(register int i=1;i<=n;++i)tp[i]=rk[i];
rk[sa[1]]=p=1;
for(register int i=2;i<=n;++i)
rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]?p:++p;
}
}//后缀排序
后缀排序ssort
先不看基数排序，现在先理解为一次rsort后，$sa$数组会更新为依据$rk$（第一关键字的排名）和$tp$（第二关键字的位置）排序后的结果。
m=75;是初始化字符集大小。
首先以第$1$位为第一关键字、位置为第二关键字排序：
for(register int i=1;i<=n;++i)rk[i]=s[i]-'0',tp[i]=i;
rsort();基数排序。
排序的变量：
for(register int k=1,p=0;p<n;m=p,k<<=1)
$k$是当前倍增长度，也就是这次排序要对前$2k$个字母排序。
$p$是一个计数器，下面要用到。
循环条件先不用管最后说，m=p是一个小优化也先不管，k<<=1每次$k$延展一倍。
现在我们有每个后缀前$k$个字符的排名情况，要扩展到$2k$上，也就是以每个后缀的前$k$位为第一关键字，$k+1\sim 2k$位为第二关键字进行基数排序。那么要先获取第二关键字的排名。
首先有的后缀长度达不到$k$个，排序时后$k$个字符是空的，认为它们排名最靠前，先加进$tp$数组里：
for(register int i=1;i<=k;++i)tp[++p]=n-k+i;
然后是重点：
for(register int i=1;i<=n;++i)if(sa[i]>k)tp[++p]=sa[i]-k;
原理中“通过$S(i)$的前$k$位排名获取$S(i-k)$的$k+1\sim 2k$位的排名”。当前$sa$存的是$S(sa[i])$的前$k$位排名，就用它更新$S(sa[i]-k)$第二关键字的排名。
rsort();基数排序。
接下来更新$rk$数组以进行新一轮的排序，需要一个新数组存一下原$rk$数组，$tp$排完序后就没用了，正好用上（$memcpy$也行）：
for(register int i=1;i<=n;++i)tp[i]=rk[i];
（最好还是不要直接$swap$两个数组，有的地方会$CE$）
初始化第一名和计数器：
rk[sa[1]]=p=1;
按$sa$依次更新$rk$，更新$rk$时要注意可能有重复的排名。
for(register int i=2;i<=n;++i)
rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;
注意$tp$数组已经赋值为原$rk$数组！
比较一下原$S(sa[i])$和$S(sa[i-1])$的前$k$个字符的$tp$，再比较一下$k+1\sim 2k$的$tp$，两个都相等说明这一轮排名相等，$p$不变；否则$++p$。
我们回过头来看循环条件：p<n。
更新完$rk$后，$p$作为计数器，意义是有多少个不同的排名。所以只要p==n即每个后缀排名都不同就排完了。
基数排序rsort
$m$为第一关键字有多少种的排名，也就是$tax$桶的上界。一开始初始化m=75即字符集大小。
前面提到的m=p即更新桶的上界。注意桶的下标是从$0\sim m$的。
先清空第一关键字的桶（$memset$也行）：
for(register int i=0;i<=m;++i)tax[i]=0;
把每个后缀的第一关键字排名加进对应的桶里：
for(register int i=1;i<=n;++i)++tax[rk[i]];
对桶做一个前缀和：
for(register int i=1;i<=m;++i)tax[i]+=tax[i-1];
做完前缀和后，每个桶的意义就变为：第一关键字排名为$i$，前面就有$tax[i]$个比它小的
最难理解的一步：
for(register int i=n;i;--i)sa[tax[rk[tp[i]]]--]=tp[i];
先复习一下定义：
$tp[i]$：第二关键字排名第$i$名的下标
一层一层看：
$i$从大到小循环：优先处理第二关键字排名靠后的
$tp[i]$：找到第二关键字排名为$i$的下标
$rk[tp[i]]$：找到它第一关键字的排名
$tax[rk[tp[i]]]$：找到对应的桶
$tax[rk[tp[i]]]—$：现在我们从这个桶里拿走它的排名。对于第一关键字比它小的，已经通过前缀和处理出来；因为是倒序循环，保证了第二关键字比它小的在它后面取到，实现了优先第一关键字排序，再以第二关键字排序。
$sa[tax[rk[tp[i]]]—]=tp[i]$：更新$sa$数组。
（模拟一下对理解很有帮助）
最后偷放一张图理解一下（来源）：
height数组
后缀数组的精髓。
性质及XJB证明：
1.$lcp(i,j)=\min\{lcp(i,k),lcp(k,j)\}(i<k<j)$
放个图会直观一些（以$aaaaabaaab$为例，下面的数组是$sa$）
抄来的证明：
设$I=S(i),J=S(j),K=S(k),p=\min\{lcp(i,k),lcp(k,j)\}$
则$I$与$K$前$p$个字符相同，$K$与$J$前$p$个字符相同。$I$与$J$最少有前$p$个字符相同。
由$p=\min\{lcp(i,k),lcp(k,j)\}$可知$I$与$K$第$p+1$个字符不相同或$K$与$J$第$p+1$个字符不相同。即$I$与$J$第$p+1$个字符不相同。
所以$I$与$J$最长公共前缀为$p$。
2.$h[i]\ge h[i-1]-1$（重点）
对于$h[i-1]\le 1$时显然成立。
考虑$h[i-1]>1$的情况：
设$k$为$sa[rk[i-1]-1]$。
则$h[i-1]=LCP(i-1,k)$
把$S(i-1)$和$S(k)$去掉首字母，得到$S(i)$和$S(k+1)$，可知$LCP(i,k+1)=LCP(i-1,k)-1=h[i-1]-1$
同时$k+1$在$sa$中一定排在$i$的前面。
上面这句话卡了我一天$QAQ$，所以详细写一下原因。
放一张图：
$S(k)$之所以排在$S(i-1)$的前面，就是在第$LCP(i-1,k)+1$的字符差异导致的。如上图灰框圈出的部分。
当去掉首字母后，因为$h[i-1]>1$，所以$S(i)$与$S(k+1)$还是会在同样的地方有差异，$rk[k+1]$还是小于$rk[i]$，$k+1$在$sa$中一定排在$i$前面。
那么所有比$i$排名靠前的里谁和$i$最像（$LCP$最大）呢？一定是和它相邻的，也就是$sa[rk[i]-1]$。
则$lcp(rk[i],rk[i-1])\ge LCP(i,k+1)$
$height[rk[i]]\ge h[i-1]-1$
$h[i]\ge h[i-1]-1$
（阳阳$2$分钟讲明白了我看了一天的证明，$TQL$！）
3.$lcp(i,j)=\min\{height[k]\}(i< k\le j)$
根据性质$1$，有：
$lcp(i,j)=\min\{lcp(i,i+1),lcp(i+1,j)\}\\ \qquad\quad\ =\min\{lcp(i,i+1),lcp(i+1,i+2),lcp(i+2,j)\}\\ \qquad\quad\ =\min\{lcp(k,k-1)\}(i<k\le j)\\ \qquad\quad\ =\min\{height[k]\}(i<k\le j)$
（还是抄的）
实现
说了那么多，怎么求$height$数组呢？
根据上面的性质$2$，就有线性时间复杂度推出$h$数组的方法，进而求出$height$数组。
当然并不需要真的开$h$数组，直接按位置循环求$height$即可。
int height[maxn];
void get_height(){
int k=0,x;//k是h[i-1]
for(register int i=1;i<=n;++i){
if(rk[i]==1)continue;
if(k)--k;//h[i]>=h[i-1]-1
x=sa[rk[i]-1];//获取待匹配的串
while(i+k<=n&&x+k<=n&&s[i+k]==s[x+k])++k;//匹配
height[rk[i]]=k;//更新height
}
}
这样就能$O(n)$求$height$啦！
应用
任意两个后缀的LCP
由性质$3$可知：
$LCP(i,j)=\min\{height[k]\}(\min\{rk[i],rk[j]\}+1<k\le \max\{rk[i],rk[j]\})$
用$ST$表$O(n\log n)$预处理，$O(1)$回答。
不同子串个数
求一个字符串本质不同的子串个数。
总子串个数为$\dfrac{n(n+1)}{2}$
每个后缀的所有前缀构成了所有子串。对于某一个后缀$S(i)$的前缀，与前面重复的个数为$height[rk[i]]$。
答案即为$\dfrac{n(n+1)}{2}-\sum\limits_{i=1}^{n}height[i]$
最长公共子串
求多个字符串的最长公共子串。
把每个字符串依次连接起来，每个串之间用一个特殊字符隔开。再给每个串的字符染上颜色。构建后缀数组。
扫一遍$sa$数组，用尺取法获取尽可能小的区间$[l,r]$使$sa[i]$$(i\in [l,r])$能覆盖所有颜色，所有的$\min\{hei[i]\}(i\in (l,r])$的最大值即为答案。用单调队列维护达到$O(\sum len(S))$。
模式串出现次数
给定一些模式串和一些母串，求每个模式串在所有母串中出现过多少次。
把所有串拼到一起建出$SA$，找到每个模式串$p$的“匹配区间”，也就是最大的区间$[l,r]$使所有的$LCP(i,p)\ge len(p)(i\in[l,r])$。答案具有单调性可以$ST$表+二分。由于模式串之间可能有子串关系，统计时染个色，模式串不加入答案，做一个前缀和就好了。
模式串出现次数（去重）
给定一些模式串和母串，求每个模式串在多少个母串里出现过。
和上面一样，二分出来区间，数颜色种数。
额。。。$HH$的项链？主席树？离线+树状数组？莫队？有那么麻烦？
好吧真的这么做。。。
可重叠最长重复子串
$\max\{height[i]\}$
不可重叠最长重复子串
二分答案。找到所有满足$\min\{height[i]\}\ge mid(i\in[l,r])$的区间（区间尽可能大），若$\max\{sa[i]\}-\min\{sa[i]\}\ge mid$则答案可行。
最长回文子串
并不会manacher和哈希所以在这里写写。
枚举一下回文中心$p$，求出翻转过来的前缀$p$与后缀$p$的$LCP$更新答案。把串翻转过来接在后面用$ST$表维护。
最小表示法
给定一个串，可以任意把最后面的字符移到开头，求能得到的字典序最小的串。
把原串复制一遍接在后面（不加特殊字符），两边染个色。找到染前半段颜色的$rk$最小的后缀就是答案。
水题
不同子串个数
就是上面应用第二个。
LCS - Longest Common Substring
两个串的$LCS$，应用第三个求解即可。
不过这个题就两个串也可以直接取$\max\{height[i]\}(col[i-1]\neq col[i])$
字符加密
把字符串复制一遍接到后面，直接后缀排序，按$sa$的顺序输出。
Sandy的卡片
多个串的$LCS$。显然两个串相同时相邻两项之间的差是相等的。
差分一下上板子就完了。
差异
$asuldb$强推此题，他说有六成$SA$的题都能转到这个题上。
求$\sum\limits_{1\le i<j\le n} len(S(i))+len(S(j))-2LCP(i,j)$
前面的$len(S(i)),len(S(j))$和系数$2$提出来，就成了求：
$\sum\limits_{1\le i<j\le n}LCP(i,j)=\sum\limits_{1\le i<j\le n}\min\{height[k]\}(i<k\le j)$
也就是$sa$里每个子区间的$min\{height[i]\}$之和。
枚举一下每个$height[i]$在哪个区间为最小值，找到左右第一个比它小的$height$，单调栈扫两遍乘起来就行了。注意处理好$height$值相同的数。
喵星球上的点名
题意概述：给一堆母串和模式串，求出每个模式串在多少个母串中出现过，每个母串包含了多少个模式串。
第一问应用里讲过了，为了处理第二问得用莫队。
第二问就是每种颜色在多少询问区间里出现过。
莫队移动指针时如果某种颜色没了，那么它就会在它上次出现的那个询问$\sim$当前询问之间的区间里出现过，然后作差加起来就完了。。。
后记：调了一晚上
，蒟蒻命要没了
仰望半月的夜空
对每个长度$L$，找到它在$sa$数组里最靠前且最大的可行区间，然后$ST$表查询这个区间的$\min\{sa[i]\}$即可。
这里可行区间就是对区间内每个后缀，截取的长度为$L$的子串相同的区间。最靠前保证了字典序最小。容易想到区间$[l,r]$满足$\min\{height[i]\}\ge len(i\in[l,r])$就是可行区间。
左端点好确定，$O(n)$扫一遍。右端点$ST$表维护$\min\{height[i]\}$+二分。
字符串
显然是要从$S(a\sim b)$和$S(c)$取$LCP$。则$S(i)$与$S(c)$的$LCP$为$\min\{LCP(i,c),b-i+1,d-c+1\}$
这个$b-i+1$是变化的，很麻烦，那么二分答案。
对于当前答案$mid$，$S(a\sim b-mid+1)$不受影响，求出这个区间内最大$LCP$值确定二分边界。
显然$sa$里离得越近$LCP$越大（废话），问题就成了求$S(a\sim b-mid+1)$谁的$rk$和$S(c)$的$rk$离得最近。
静态区间前驱后继，上主席树就是了。
复杂度$O(n\log^2 n)$，有点卡常。。。
弦论
$t=0$时造出$SA$求出$height$数组。枚举答案所在的后缀，$S(sa[i])$前有$\sum\limits_{j=1}^{i-1} len(S(sa[j]))-height[j]$个子串比$S(sa[i])$的子串小。
$t=1$，$emm…$学了$SAM$再做，先咕了。
$update$：填坑
