广义后缀自动机总结
我们在做后缀自动机的题目的时候，都是对一个串构造后缀自动机，那么该如何对多个串建出后缀自动机呢？
那就是广义后缀自动机。首先我们考虑一个暴力的建造方法，就是每次建完一个串以后就把last指针移到root上面，接着建下一个串。
发现时间复杂度其实依旧是$O(n)$，而且匹配也不会出现啥问题。
但是这样新加入一个点的时候可能已经有这个转移了，那该怎么办呢？
其实和后缀自动机的建法是一样的，首先看max集合是不是等于pre的max+1，假如等于的话这个节点就已经很合适了，而且Parent都找好了，就不用进行其他的操作了。
不等于的话还是需要新建一个辅助节点，而且我们已经找好了它的Parent，就是这个点的Parent。
当然，我们可以忽视不用创建节点的情况，每次都创建一个节点，后果就是有可能它的max跟它的父亲相同，这样没有状态能转移到它，它也不表示任何一个子串，它存在的意义只是为它的祖先贡献了的right集合一个位置，当然它在parent树中还必须起一个连接作用。代码可以完全不改变。
而按照最简状态后缀自动机的定义，这种状态是不应该存在的，但是存在的话问题也不大。因为空间其实最大就是2n的。。
下面就是构建代码
void insert(int x)
{
int now=ch[last][x],pre=last;
if (now)
if (dis[now]==dis[pre]+1) last=now;
else
{
int nows=++sz;dis[nows]=dis[pre]+1;
memcpy(ch[nows],ch[now],sizeof ch[now]);
fa[nows]=fa[now],fa[now]=nows;
for (;pre && ch[pre][x]==now;pre=fa[pre]) ch[pre][x]=nows;
last=nows;
}
else
{
now=++sz,dis[now]=dis[pre]+1;last=now;
for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
if (!pre) fa[now]=root;
else if (dis[ch[pre][x]]==dis[pre]+1) fa[now]=ch[pre][x];
else
{
int q=ch[pre][x],nows=++sz;dis[nows]=dis[pre]+1;
memcpy(ch[nows],ch[q],sizeof ch[nows]);
fa[nows]=fa[q],fa[q]=fa[now]=nows;
for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
}
}
}
现在就做了两个题