广义后缀自动机

含义：在多个字符串中建立自动机。

做法（与后缀自动机的不同）：

1. 在每加入一个新字符串时将 last 设为 1。
2. 再加入时先判断现在 last 节点是否有当前要加入的儿子。（1）如果没有，按正常后缀自动机进行操作。（2）如果有，且当前儿子的len为last的len+1，则此节点已有等效节点，跳过即可。（3）如果不等，则要将此时last的相应儿子进行拆分，进行和后缀自动机同样的操作。

关键代码：

void ad(int x)
{
     if(a[last].ch[x])
     {
       if(a[last].len+1==a[a[last].ch[x]].len)
       {
           last=a[last].ch[x];
           return;
       }
       int t1=a[last].ch[x],t2=++tot;
       a[t2]=a[t1];
       a[t2].len=a[last].len+1;
       a[t1].fa=t2;
       for(;last&&a[last].ch[x]==t1;last=a[last].fa) 
       a[last].ch[x]=t2;
       last=t2;
       return;
     }
     int p=last,k=last=++tot;
     a[k].len=a[p].len+1;
     for(;p&&!a[p].ch[x];p=a[p].fa) a[p].ch[x]=k;
     if(!p) a[k].fa=1;
     else{
         int t1=a[p].ch[x];
         if(a[t1].len==a[p].len+1) a[k].fa=t1;
         else{
             int t2=++tot;
             a[t2]=a[t1];
             a[t2].len=a[p].len+1;
             a[t1].fa=a[k].fa=t2;
             for(;p&&a[p].ch[x]==t1;p=a[p].fa) 
             a[p].ch[x]=t2;
         }
     }
}

例题：

咕。。

广义后缀自动机

原文：https://www.cnblogs.com/ezuyz/p/15086116.html