广义后缀自动机
含义:在多个字符串中建立自动机。
做法(与后缀自动机的不同):
- 在每加入一个新字符串时将 last 设为 1。
- 再加入时先判断现在 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;
}
}
}
例题:
咕。。