字尾自動機不是Trie樹上的,蒟蒻的我才知道。
那個樹叫parent。
代碼(增量構造):
namespace SAM{
sant s[3000000];
int siz;
int fin;
lnt ans;
void Insert(int c)
{
int nwp,lsp,nwq,lsq;
nwp=++siz;
s[nwp].len=s[fin].len+1;
for(lsp=fin;lsp&&(!s[lsp].tranc[c]);lsp=s[lsp].pre)
s[lsp].tranc[c]=nwp;
if(!s[lsp].tranc[c])
s[lsp].tranc[c]=nwp;
else{
lsq=s[lsp].tranc[c];
if(s[lsq].len==s[lsp].len+1)
s[nwp].pre=lsq;
else{
nwq=++siz;
s[nwq]=s[lsq];
s[lsq].pre=s[nwp].pre=nwq;
s[nwq].len=s[lsp].len+1;
while(s[lsp].tranc[c]==lsq)
{
s[lsp].tranc[c]=nwq;
lsp=s[lsp].pre;
}
}
}
fin=nwp;
return ;
}
};
有些算法是建構在parent樹上的(類似trie圖中的fail樹)。
廣義字尾自動機:
1 void Insert(int c)
2 {
3 int nwp,lsp,nwq,lsq;bool flag(false);
4 if(s[fin].tranc[c]&&s[s[fin].tranc[c]].len==s[fin].len+1)
5 {
6 nwp=s[fin].tranc[c];
7 return ;
8 }//特判1
9 nwp=++siz;
10 s[nwp].len=s[fin].len+1;
11 for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre)s[lsp].tranc[c]=nwp;
12 if(!lsp)s[lsp].pre=1;
13 else{
14 lsq=s[lsp].tranc[c];
15 if(lsq].len==s[lsp].len+1)s[nwp].pre=lsq;
16 else{
17 if(s[nwp].len==s[lsp].len+1)flag=true;
18 nwq=++siz;
19 s[nwq]=s[lsq];
20 s[nwq].len=s[lsp].len+1;
21 s[nwp].pre=s[lsq].pre=nwq;
22 while(s[lsp].tranc[c]==lsq)
23 {
24 s[lsp].tranc[c]=nwq;
25 lsp=s[lsp].pre;
26 }
27 }
28 }
29 if(flag)fin=nwq;//特判2
30 else fin=nwp;
31 return ;
32 }
轉載于:https://www.cnblogs.com/blog-Dr-J/p/10013968.html