介绍

首先后缀自动机

可以包括给定字符串的所有子串
O(n)
是自动机

一些定义

endpos

字符串s的一个子串t，endpos(t)为s中t的所有结束位置构成的集合

SAM是一个最小的DFA

有向无环图

节点是状态，边是转移

转移是一些字母

从源点出发到终止状态所有转移连起来的字符串t是字符串s的一个后缀

SAM的节点最小

那么如果endpos(t1)=endpos(t2)，那么他们就在一个等价类中

一堆引理

两个非空子串u，w (|u|<=|w|) endpos相同，只有u在s中每次出现都是以w的后缀出现的
那么就可以推出来：考虑u，w (|u|<=|w|) 只有2种可能
- endpos(u),endpos(w)不相交
- endpos(w)是endpos(u)的子集
一个endpos等价类里边，所有子串长度不同，而且差值为1，正好覆盖区间

然后就有我们的后缀link

对于一个不是源点的状态v，然后考虑这个endpos等价类中最长的字符串w，其他的就是w后缀了捏

然后我们有

w开始，有一个连续区间长度的后缀也都是这个等价类里边的玩意，定义最长的一个不是等价类里边的后缀为t，把v的后缀link到t上

显然最后是link到源点的

最后这玩意就构成了一个树

然后我们就可以开始算法本身了捏

算法实现

哥们看不懂捏

首先说重点

后缀link树和后缀自动机共同相同的节点，不同的只是转移的边不同

大概步骤

首先，这个是在线算法，我们每次往自动机里加入一个字符，然后维护SAM

首先定义初始状态

这个点编号0，len=0，fa=0

然后我们就能挨个加入字符c了

有以下流程

首先我们加入了一个新字符，那么新串对应的的endpos是新的长度，以前不存在，因此我们新建一个状态np，之前整个旧串对应的状态记为p，很显然len(q)=len§+1

然后对于新加入的字符c，我们进行以下操作

如果p没有一个字符c的出边(这里是自动机的边)，就在link树上到他的父节点，也就是后缀link的点，一直循环直到p到达初始状态的节点或者有一个字符c的出边

这个操作其实是压缩遍历旧串的所有后缀x，然后看是否存在一个x+c在旧串种就存在了，因为引理中已经提到，每个状态link到的节点都是当前状态的后缀，所有我们从p上来肯定是旧串的后缀了捏

途中我们把经过每个没有c出边的p都连一个c到np

然后我们就有3种情况

Case 1

p到初始状态都没有c的出边

np状态直接link到初始状态

Case 2

找到了一个p，有c的出边，到达一个新状态q，且len( q )=len( p )+1

首先我们知道p是旧串后缀，q是p的字符串+c，因此q是新串的后缀，那么我们理所当然把np link 到q上就行了

Case 3

和case2差不多，但是找到的p出边到达的q没有len( q )=len( p )+1

或者说，len( q )>len( q )+1

这时候我们要把q拆成两个点，是新串后缀的和不是的，然后link就行

具体来说，定义一个新点nq，len=len§+1,出边转移和q相同，link 到p上，然后np和q都link到nq上

最后稍微更新下转移边，p往上走，把所有p link 到q的转移 link 到nq上就行了

最后稍微提一下如何计算每个状态的endpos大小

设想一下，我们每次加入一个字符c，肯定会出现一个新的endpos，而且他能够对往上走到源点经过的所有节点都产生影响，也就是说我们使用一个数组f[i]来统计endpos，加入新字符时让f[np]=1,最后跑一下dfs，f[i]=f[i]+sum(f[i所有的儿子]) 即可捏

或者把sam的点按len排序(可以用桶排) 从大到小更新 **f[sam[i].fa]+=f[i]**也行

code

先贴一手毛的板子

struct NODE
{
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=0;}
}sam[MAXN<<1];
int lst=1,tot=1;
void add(int c)
{
    int p=lst;int np=lst=++tot;
    sam[np].len=sam[p].len+1;
    for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;
    if(!p)sam[np].fa=1;//以上为case 1
    else
    {
        int q=sam[p].ch[c];
        if(sam[q].len==sam[p].len+1)sam[np].fa=q;//以上为case 2
        else
        {
            int nq=++tot;sam[nq]=sam[q];
            sam[nq].len=sam[p].len+1;
            sam[q].fa=sam[np].fa=nq; 
            for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;//以上为case 3
        }
    }
}

暂时先写这么多，乏了，早上写一手题以及用法吧