目录
咕咕日报上的，就没有一个是差品：https://www.luogu.org/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie，同时，带luogu水印的图也是一律采用这个博客的，因为我太弱了，不会画图QAQ。
时间复杂度的证明https://blog.csdn.net/qq_35649707/article/details/66473069
广义后缀数组就是在这学的：https://blog.csdn.net/litble/article/details/78997914
字符集的相关内容：https://oi.men.ci/suffix-automaton-notes/
套B-树：https://www.cnblogs.com/hyghb/p/8445112.html
stO 后缀自动机怎么能少了陈立杰大佬的论文了呢? Orz
博主是真的臭不要脸，拿着别人的图写着自己的博客
其实许多题目，我们都可以用后缀数组做，但是后缀数组有时候远远不能满足我们的需求，这个时候，后缀自动机就出现了。
问题描述
给出一个字符串S(S<=250000)，令F(x)表示S的所有长度为x的子串中，出现次数的最大值。求F(1)..F(Lengh(S));
样例输入
ababa
样例输出
3
2
2
1
1 首先，我们要定义一个东西，叫\(right\)，字符串的每个子串都可以有个\(right\)。
\(right(s)\)表示的是\(s\)子串在母串所有出现位置的右端点。
打个比方：在\(ababa\)中，\(right(ab)={2,4}\)
加入有两个不相同的子串的\(right\)集合是相等的，那么必然一个是另外一个的后缀。
这个挺好证的，感性理解最好，画个图就知道了。
我们把所有相同的\(right\)集合叫做一个等价类。
如图，\(ab,b\)就是在一个等价类里面。
两个\(right\)集合，要么两个集合没有相同的数字，要么一个集合是另外一个集合的子集。
这个也挺好证的，用反证法，如果\(right\)集合中有一个相等的，那么我们就可以进而推出一个是另外一个的后缀（自己想想看是不是），那么在想想看是不是一个子串的\(right\)是不是就是那个作为后缀子串的\(right\)的子集。
对于每个\(endpos\)（等价类）而言，里面所包含的子串的长度应当是连续的。
假设子串的长度是不连续的，那么设这个不在里面的子串是\(s\)，那么比他短的子串在这个等价类里面，也就是说只有这个\(right(s)\)数字的个数小于\(endpos\)里面子串\(right\)的数字个数，才可以，但是比他长的子串也在里面，而这个子串无一例外是这些比他长的子串的后缀，所以只能数字个数只能等于，所以这个\(s\)应当在等价类里面。
等价类点的个数的数量级是\(O(n)\)的。
我们可以发现，在一个\(endpos\)里面最长的子串前面加一个字符，就是另外一个\(endpos\)里面的，而这个\(endpos\)里面的\(right\)集合应该是原来\(endpos\)里面的\(right\)集合的子集，因为这个新子串要出现肯定是要这个旧子串的基础上还有个字符相等才可以的。
而我们在旧子串前面添加另外一个不一样的字符，得到的\(endpos\)的\(right\)和原来的新子串\(endpos\)的\(right\)是不相交的，怎么可能有个位置使得两个长度相同但不一样的子串都出现呢？
所以我们可以知道，一个等价类的\(right\)集合通过正确的分割，可以分割成几个其他\(endpos\)的\(right\)集合。
那么从\({1,2,3,...,n}\)，开始分割，最多也只能像线段树那样分（为什么，倒着想，两个叶子结点就可以产生一个父亲节点，这是最多的合并方案了），也是最多就\(O(n)\)个罢了，所以节点数量最多\(O(n)\)。
而这个巧妙的分裂方案又呈现出一个树的样子，那么我们就给这棵树起个文雅点的名字：\(Parent Tree\)。
同时一个字符串只有唯一的\(Parent\)树，因为等价类的划分只有一个。
LOOK一下\(aababa\)的\(Parent\)树
点里面的就是\(right\)集合，什么？\(1\)的点为什么不见了？因为\(right\)为\(1\)的子串为\(a\)，很不巧的是刚好被\(1,2,4,6\)给包含了进去，但是并不会影响我们，只要以后想题的时候注意一下就行了。
我们设等价类里面最长的子串长度是\(len\)，最短的是\(minlen\)，那么\(len(fa(x))+1=minlen(x)\)，其实这个也挺好证明的，儿子最短的子串就是自己最长的子串加一个字符吗，对吧。
我们都知道，有个强大的Trie，我们可以把一个字符串的每个后缀插入进去，然后就成了这样(aabab)：
他可以支持查询任意一个子串，子串个数等等操作。
为什么？
因为他有以下的性质：
但是点的个数是\(O(n^2)\)的，那么我们要如何处理这个问题呢。
那么我们就得找到一个符合这个性质的一个好东西。
而且我们也发现上图中的\(abab\)中的\(bab\)可以和其他的\(bab\)结合的。
也就是说我们可以找到一个在\(DAG\)上的一种算法，而不是一棵树。
当然也就是后缀自动机，同时因为他有更多的性质，使得他更加的强大。
当然，特别巧的是，后缀自动机的节点就是\(Parents\)树上面的，边就不是了，边就让我们和眼花缭乱了，而在构造的时候，我们也是用两种理论互相完善形成的。
给出一个图：
谈到鸡就不禁想到了jntm，自动jntm？
首先，自动机一般有这么五个东西：初始状态，状态集合，结束状态，转移函数，以及字符集。
那么字符集我们知道，初始状态和结束状态呢？初始状态我们设为空串，也就是\(right\)集合\({1,2,3,4...,n}\)，而结束状态则是集合内一个个的后缀，也就是\(Parent\)树中\(right\)集合为\(n\)的以及他的父亲与祖先，除了根节点。
而转移呢，从一个节点\(x\)到另外一个节点\(y\)连一条为\(c\)的边出来，表示的是\(x\)包含的所有子串在后面加上\(c\)后都是\(y\)中所包含的子串（但\(y\)中的子串去掉最后一个字符不一定是\(x\)中的子串，只有可能是\(x\)儿子所包含的子串）。
字符集不就是那个母串吗。
大佬：还以为有多术语，没想到还是口头语。
那么一个成型的后缀自动机大概长这样：
橙点是结束状态，每个点旁边的红色字符串表示的是最长的子串。
我们回想起来后缀自动机必须遵循的几个性质：
前面三个都可以手动满足，但是在满足前三个性质后，第四个性质能不能满足？
我们可以发现每个\(endpos\)所含的子串都是不同的，但是同时所有\(endpos\)所含的子串累加起来就是母串的所有不重复子串数量的和。
所以转移我们都是在一部分子串的后面加上一个字符到达的，不可能有两个点含有相同的子串，而且到达一个点形成的子串只能是这个点\(endpos\)所含有的，这不就证出来了？
我不敢保证绝对唯一，只能证在\(Parent\)树上的后缀自动机是绝对唯一的，首先\(Parent\)树是唯一的，而能指向一个\(endpos\)的\(endpos\)数量也是固定的，所以后缀自动机是唯一的。（好草率呀。）
这里总结一下性质，方便下个证明（Trie的性质就不搬了，反正后缀自动机也是满足的），也方便做题：
后缀自动机边的数量级是\(O(n)\)的，为什么，我们对一个后缀自动机求一个生成树出来，删掉其他的边。
然后从每个终点往源点跑自己所包含的子串，往回跑的意思是找到跑到这个终点能形成这个子串的路径，然后往会跑，允许找不到的路可以往回走的时候，可以添加一条边回来，那么我们就可以再次走完一个子串，但是可能不是这个子串，但是我们可以先把走完的子串划掉，然后再跑现在的子串，可以证明，跑完这个终点所有的子串（其实就是母串的后缀），添加回来的新边不会超过这个终点所包含的子串个数。
大家弄不懂为什么添加了一条边就又可以跑出一个子串出来？我们看一下，在生成树上多连一条边出来，那么是不是就是多了一条路径可以到终点了？根据前面的性质我们知道肯定是个不同的子串，所以就可以跑出一个新的子串，所有的终点跑完后，添加的边数不超过\(n\)条（其实这个利用性质的证法我认为更简单，也是我的证法）。
所以数量级为\(O(n)\)。
这里草率的放个形象生动的生成树例子在这，因为我觉得我的证法好像和他的不是很一样。
橙点是终点，神奇颜色的点是源点，黑边是生成树的边，蓝边是要添加回来的边，绿边是删掉未添加回来的边，箭头指向的就是目前要跑的终点，注意是反着跑。
图可能画的不是很标准，只是为了呈现出一个加边多路径的一个情况出来。
我们会发现，加了一条边，就多出现了一条路径，也就多了个子串可以走回去。
所以我们就证明出来了。
终于到了最后的时刻，通过看大佬的博客，我发现代码放前面更容易帮助人理解构造的过程。
所以先放上代码。
struct node
{
int a[30],len,fa;
}tr[N];int tot=1,last=1;
void add(int c)
{
int p=last;int np=last=++tot;
tr[np].len=tr[p].len+1;
for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;
if(!p)tr[np].fa=1;
else
{
int q=tr[p].a[c];
if(tr[q].len==tr[p].len+1)tr[np].fa=q;
else
{
int nq=++tot;
tr[nq].fa=tr[q].fa;tr[q].fa=nq;
tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a));
tr[np].fa=nq;
for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;
}
}
}后缀自动机的构建是在线的，也就是把字符串一个个字符丢进去，进行构建。
我们跟着KesdiaelKen大佬一起，分成一个个部分来进行传教讲课。
int p=last;int np=last=++tot;
tr[np].len=tr[p].len+1;我们知道，扔进去一个字符，那么会改变的肯定就是原字符串的后缀，那么我们就用\(las\)记录包含有原字符串母串的点是哪个点，然后新点\(np\)的最长子串的长度就是新串的长度就是旧串的长度+1。
for(;p && !tr[p].a[c];p=tr[p].fa/*fa表示的是Parent树中的*/)tr[p].a[c]=np;我们通过跳\(p\)的父亲，使得每一个原本的终点（含有后缀的点）都有一条指向\(np\)的边，也就是使所有原本的后缀都可以跳到现在的后缀集合。
\(!tr[p].a[c]\)这句话是什么意思呢？如果有个终点也有一条边是指向\(c\)的，首先可以说明的是这个终点包含的后缀在原串中出现了至少两次，否则在旧串中一个后缀，是不可能再在后面加点的，而且也说明了，新串的后缀有一部分已经出现过了，就要进行一些新的判断了。
if(!p)tr[np].fa=1;
else很简单，说明原串从未有\(c\)这个数字出现（有的话\(1\)号点会指过去），所以这个新串的所有后缀都在一个\(endpos\)里面，也就是说新串只有一个终点。
当然，跳进了那个\(else\)的话，就代表了新串也不只有一个终点了。
int q=tr[p].a[c];
if(tr[q].len==tr[p].len+1)tr[np].fa=q;首先，我们知道\(p\)所代表的子串都是旧串的后缀，如果\(q\)的最长长度是\(p\)的\(+1\)，那么说明\(q\)所代表的的子串都是旧串的后缀\(+c\)，自然\(np\)就可以认他做父亲。
这是你又会问了，但是\(q\)只能代表\(np\)的一些后缀呀，比如新串是\(dbcabcabc\)，然后假设\(q\)表示的是\({bc}\)这个后缀，但是他有个儿子（\(Parent\)树的儿子）表示的又是\({abc}\)，那么根据后缀自动机\(np\)不应该认这个儿子吗？
设这个儿子为\(q'\)，我们知道后缀自动机的话层数越深，所代表的子串长度越长，那么指向\(q'\)的一个后缀应该是\(ab\)，那么理论上将找到\(ab\)会比找到\(b\)更先，所以认的原本就是最儿子的那个。(:雾
但是你认完了以后也没有继续去上面更新又是怎么一回事，因为上面的后缀肯定都是小于\(tr[p].len\)的了，也就是说以后如果要找新串后缀的话，如果长度小于等于\(tr[q].len\)的话，那么找到的自然就是\(q\)了，那么我们还何必屁颠屁颠的再去加一种方式呢？破坏性质还变慢，赔了夫人又折兵。这么亏的勾当我们才不做呢，认完就完事了。
int nq=++tot;
tr[nq].fa=tr[q].fa;tr[q].fa=nq;
tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a));
tr[np].fa=nq;
for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;那么如果\(tr[q].len≠tr[p].len+1\)，我们知道，这个时候只有\(tr[q].len>tr[p].len+1\)的情况了。
但是同时这个长的串也不是新串后缀，为什么？因为如果是的话，去掉最后一个字母比\(tr[p].len\)还大，所以应该先被跳到才对，为什么现在还没有被跳到呢？因为这个长的串由最后\(tr[p].len+1\)个字母组成的后缀是新串后缀，但是这个长的串不是。
那么我们就涉及到了一个问题了，这个点现在出现了锅了，我们需要把他拆成两个点了，因此申请了一个\(nq\)，然后\(nq\)表示的就是这个点的\(tr[p].len+1\)的后缀以及更短的后缀，因为这些子串在后面又出现了一次，而\(q\)因为少了这一次，所以他的\(right\)是\(nq\)的子集，理所应当成为了他的儿子，而根据分割要求，所以\(nq\)的\(right\)还有个数字没有分出去，就是现在新串的长度，刚好，我们的\(np\)的父亲也可以认到\(nq\)身上，这不就解决了吗。
同时虽然分开了，但是能在后面添加的数字还是可以添加的，于是我们可以把\(q\)的\(a\)数组直接拷贝到\(nq\)上面去。
不对，还有个问题，\(p\)以及\(p\)的父亲祖先的\(c\)都指向了\(q\)，那么因为\(q\)以前包含了\(tr[p].len+1\)这个长度的后缀，但是现在没有了，跑到\(nq\)上去了，所以我们自然需要用到for然后去更新一下父代。
那么这不就好起来了吗？QMQ
而例题，则十分的明显，就是叫我们把每个点的\(right\)集合处理出来，然后拿集合大小去更新\(ans[tr[i].len]\)，然后再把\(ans\)从上到下更新一遍。
我也忘记了我到底想到了一个什么SB的思路，反正忘记了，就不管了吧。
正解就是每次在创\(np\)是，对\(np\)的\(right\)集合的个数++，我们可以知道，一个非叶子结点，他的\(right\)集合的大小就是所有儿子的\(right\)集合的大小，加上自己本身的\(right\)集合的大小。
为什么要算上自己的，自己的不是没有嘛，因为存在掉叶子结点的情况，上文我们有提到\(1\)的叶子结点被包括在了其他节点里面，这就是我所说的考虑这种情况，这种情况一般不会对结果造成影响，但是过程可能要有点变动。
#include<cstdio>
#include<cstring>
#define N 510000
using namespace std;
struct node
{
int a[30],len,fa;
}tr[N];int tot=1,last=1;
char st[N];int n;
int dp[N],r[N];
void add(int c)
{
int p=last;int np=last=++tot;r[np]++;
tr[np].len=tr[p].len+1;
for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;
if(!p)tr[np].fa=1;
else
{
int q=tr[p].a[c];
if(tr[q].len==tr[p].len+1)tr[np].fa=q;
else
{
int nq=++tot;
tr[nq].fa=tr[q].fa;tr[q].fa=nq;
tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a));
tr[np].fa=nq;
for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;
}
}
}//后缀自动机
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int cs[N],sa[N];
int main()
{
scanf("%s",st+1);n=strlen(st+1);
for(int i=1;i<=n;i++)add(st[i]-'a');
for(int i=2;i<=tot;i++)cs[tr[i].len]++;
for(int i=1;i<=n;i++)cs[i]+=cs[i-1];
for(int i=2;i<=tot;i++)sa[cs[tr[i].len]--]=i;
int p=1;
for(int i=tot;i>=1;i--)r[tr[sa[i]].fa]+=r[sa[i]];//以上按深度排序的部分其实是可以直接一发DFS暴力解决的，但是这样打也可以。
for(int i=2;i<=tot;i++)dp[tr[i].len]=mymax(dp[tr[i].len],r[i]);
for(int i=1;i<=n;i++)printf("%d\n",dp[i]);
return 0;
}你问我时间复杂度？我们可以发现能影响时间复杂度的就这两句话：
for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;
for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;第一句因为是加边，所以不会总体不会大于\(O(n)\)。
更严谨的证明，跳\(for\)循环\(last\)的层数会减，而二操作最多层数\(+1\)，所以是\(O(n)\)
第二句话我们考虑\(short(x)\)表示的是\(x\)这个点的最短子串的长度\(，\)fa(x)\(为\)tr[x].fa\(，那么我们接着考虑一下\)short(fa(last))$会有怎样的变化。
我们知道原循环有两个\(if\)，两个\(else\)，三种情况。
如果跳到第一种情况，那么\(short(fa(last))\)就会等于0.
如果在第二种情况，我们考虑一下\(p\)在哪，在加字符前，我们会发现\(short(p)<=short(fa(last))\)，为什么会相等，因为\(p\)有可能就是\(fa(last)\)，然后跳到了\(q\)，因为只加了一个字符，所以\(short(q)<=short(p)+1\)，所以在我们可以知道\(short(nq)<=short(fa(last))\)（没加新字符的\(last\)），所以我们就可以知道，在第二种情况下，我们的\(short(fa(last))\)会\(+1\)或者更小。
第三种情况下，我们同样可以知道\(short(q)<=short(p)+1\)，然后把\(q\)拆成了\(q\)和\(nq\)，同时我们不是要往上跳吗，我们知道中父亲的short肯定是比儿子要少\(1\)的（不管是Parent Tree还是后缀自动机），然后我们也知道这个for循环的重定向是把原来指向\(q\)的指向与\(nq\)了。
而我们的for会跳几层几层呢？仔细想想最多不就是\(short(p)+1-short(q)+1\)吗，因为你从\(p\)开始跳的话，\(short(p)\)会不断减少，如果\(short(p)+1\)还小于\(short(q)\)的话，那么不就指不到\(q\)了吗，所以只会跳\(short(p)-short(q)+2\)，而最坏情况\(short(p)=short(fa(last))\)，而我们新的父亲就是\(nq\)，仔细想想发现跳的次数\(-1\)就是\(last\)减少的个数。
所以总结下来，\(n\)次调用，最多出现\(n\)个\(1\)，所以减少的也是最多\(n\)次，可以得出为\(O(n)\)。
中间不是有个拷贝吗？但是那是字符集的大小，也就是说字符集固定的话复杂度是线性的。
不固定呢？我们可以给每个节点用map呀，当然也有大佬用B-树的。
这里用上https://www.cnblogs.com/hyghb/p/8445112.html大佬的话
首先，我们曾经说过要保证字母表的大小是常数。否则，那么线性时间就不再成立：从一个顶点出发的转移被储存在B-树中，
它支持按值的快速查找和添加操作。因此，如果我们记字母表的大小是k，算法的渐进复杂度将是O(n*logk)，空间复杂度O(n)。但
是，如果字母表足够小，就有可能牺牲部分空间，不采用平衡树，而对每个节点用一个长度为k的数组（支持按值的快速查找）和一
个动态链表（支持快速遍历所有存在的键值）储存转移。这样O(n)的算法就能够运行，但需要消耗O(nk)的空间。
因此，我们假设字母表的大小是常数，即，每个按字符查询转移的操作、添加转移、寻找下一个转移——所有这些操作我们都
认为是O(1)的。我们只要每次塞入一个字符串之后，然后把last=1，然后再塞，仔细想想也满足能都识别任意一个字符串的子串。
我们给每个点开个\(set\)存一下以这个点包含的所有串为子串的字符串有哪些，这些可以直接用启发式合并合并出来，如果大于等于\(k\)的话，那么我们就处理他的val为他所包含的字串个数。
然后我们可以知道一件事情，就是加入一个点是可以的话，那么再Parent树的父亲也满足条件，而且我们知道Parent树中一个点的子树里面所有由\(np\)组成的点（不包括\(nq\)的点）的个数就是这个点\(right\)集合的个数，所以我们只要DFS遍历一下统计答案。
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#define N 210000
using namespace std;
struct node
{
int y,next;
}a[N];int len,last[N];
void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
struct SAM
{
int a[30],len,fa,id;
}tr[N];int tot=1,las;
set<int>ss[N];
void add(int id,int c)
{
int p=las;int np=las=++tot;
tr[np].len=tr[p].len+1;ss[np].insert(id);tr[np].id=id;
for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;
if(!p)tr[np].fa=1;
else
{
int q=tr[p].a[c];
if(tr[q].len==tr[p].len+1)tr[np].fa=q;
else
{
int nq=++tot;
tr[nq].fa=tr[q].fa;tr[q].fa=nq;
tr[nq].len=tr[p].len+1;
memcpy(tr[nq].a,tr[q].a,sizeof(tr[nq].a));
tr[np].fa=nq;
for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;
}
}
}
set<int>::iterator ii;
long long val[N];int n,m;
void dfs1(int x)
{
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
dfs1(y);
if(ss[y].size()>ss[x].size())swap(ss[x],ss[y]);//减少常数
for(ii=ss[y].begin();ii!=ss[y].end();ii++)ss[x].insert(*ii);
ss[y].clear();//顺便清空
}
if(ss[x].size()>=m)val[x]=tr[x].len-tr[tr[x].fa].len;
}
long long ans[N];
void dfs2(int x,long long zz)
{
zz+=val[x];
if(tr[x].id)ans[tr[x].id]+=zz;//说明他是np
for(int k=last[x];k;k=a[k].next)dfs2(a[k].y,zz);
}
char st[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
int slen=strlen(st+1);las=1;//别忘了
for(int j=1;j<=slen;j++)add(i,st[j]-'a');
}
for(int i=2;i<=tot;i++)ins(tr[i].fa,i);
dfs1(1);dfs2(1,0);
for(int i=1;i<n;i++)printf("%lld ",ans[i]);
printf("%lld\n",ans[n]);
return 0;
}这里说说，子序列按顺序，但是不一定是连续的，懂吧。
放上https://blog.csdn.net/litble/article/details/78997914的介绍，写的很好
后缀自动机的一条路径是原串的一个子串，那么序列自动机上的一条路径就是原串的一个子序列
序列自动机很好写，就是每次查看最后出现过的一些表示字母x的节点，如果它们没有当前插入的字符y的儿子，那么就将它们的y儿子赋为当前节点，显然这样可以表示出原串的所有子串。
void ins(int x) {
++SZ,pre[SZ]=last[x];
for(RI i=0;i<26;++i) {
int now=last[i];
while(!ch[now][x]) ch[now][x]=SZ,now=pre[now];
}
last[x]=SZ;
}
简(kun)单(nan)到让我开(jue)心(wang)的后缀自动机全家桶（普通后缀、广义后缀、子序列）
原文：https://www.cnblogs.com/zhangjianjunab/p/11411543.html