每次让last=1的写法是否也是正确的，只要像您那样判断last是否有出边就可以
by HikariS @ 2021-06-15 16:17:41
节点数是6
by Pecuria @ 2021-06-15 16:17:45
@[Tamaki_Iroha](/user/103627)
pos[i] 表示字典树上点 $i$ 对应的后缀自动机上的点。
by ix35 @ 2021-06-15 16:22:03
贴一下我的代码吧，基本照着题解写的，对您这组数据我给出的节点数是6（在线做法）。
和您的解决方案是一样的。
```cpp
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
ll c[2000005][27],len[2000005],tot=1,rt=1,ans,n,fa[2000005],lm;
char s[2000005];
ll insert(ll x,ll last){
if(c[last][x]&&len[last]+1==len[c[last][x]]) return c[last][x];
ll now=++tot,ad,prt,flag=0;
len[now]=len[last]+1;
while(last&&!c[last][x]){
c[last][x]=now;
last=fa[last];
}
if(!last){
fa[now]=rt;
}
else{
prt=c[last][x];
if(len[prt]==len[last]+1) fa[now]=prt;
else{
if(len[now]==len[last]+1) flag=1,ad=now;
else ad=++tot;len[ad]=len[last]+1;
for(ll i=1;i<=26;i++) c[ad][i]=c[prt][i];
fa[ad]=fa[prt];fa[prt]=ad;if(!flag) fa[now]=ad;
while(last&&c[last][x]==prt){
c[last][x]=ad;
last=fa[last];
}
}
}
return now;
}
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%s",s+1);
lm=strlen(s+1);
ll last=1;
for(ll t=1;t<=lm;t++){
last=insert(s[t]-'a'+1,last);
}
}
for(ll i=1;i<=tot;i++){
ans+=len[i]-len[fa[i]];
}
printf("%lld",ans);
}
```
by Pecuria @ 2021-06-15 16:23:45
代码：
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#include <bits/stdc++.h>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5,M=1e6+3;
int n,t;char ch[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Trie{
int O,c[M],fa[M],tr[M][26];
//fa[x]: Trie树上x的父节点
//c[x]: Trie树上x的颜色
Trie(){O=1;}//根初始化为1
inline void insert(char ch[]){
Re p=1;
for(Re i=1;ch[i];++i){
Re a=ch[i]-'a';
if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
p=tr[p][a];
}
}
}T1;
struct Suffix_Automaton{
int O,pos[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
//pos[x]:Trie上的x节点（路径1->x所表示的字符串）在SAM上的对应节点编号
//link[i]: 后缀链接
//trans[i]: 状态转移数组
Suffix_Automaton(){O=1;}//根初始化为1
inline int insert(Re ch,Re last){//和普通SAM一样
Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return z;
}
inline void dfs(Re x){
for(Re i=0,to;i<26;++i)if(to=T1.tr[x][i])
pos[to]=insert(T1.c[to],pos[x]),dfs(to);
}
inline void build(){pos[1]=1,dfs(1);}//dfs遍历Trie树构造广义SAM(Tire树上的根1在SAM上的位置为根1)
inline void sakura(){
LL ans=0;
for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
printf("%lld\n",ans);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch);
SAM.build();
cout << "Edge: " << endl;
for (int i=1;i<=SAM.O;i++) {
for (int j=0;j<26;j++) {
if (SAM.trans[i][j]) {cout << i << " " << (char)(j+'a') << " " << SAM.trans[i][j] << endl;}
}
}
cout << "Link: " << endl;
for (int i=2;i<=SAM.O;i++) {
cout << "link[ " << i << " ] = " << SAM.link[i] << endl;
}
cout << "Pos: " << endl;
for (int i=1;i<=T1.O;i++) {
cout << "pos[ " << i << " ] = " << SAM.pos[i] << endl;
}
return 0;
}
```
by ix35 @ 2021-06-15 16:24:02
@[Tamaki_Iroha](/user/103627)
那就说明您学的是对的啊
by ix35 @ 2021-06-15 16:24:39
@[ix35](/user/113546) 只能说明博主在写离线dfs做法的时候写挂了，但是题解本身是没问题的。
但是离线dfs做法时间复杂度就是错的。
by Pecuria @ 2021-06-15 16:28:39
看了一下题解对离线做法的解释，确实没有说过要写特判。
不过我一直都写的在线所以一直没觉得有什么问题。
by Pecuria @ 2021-06-15 16:32:41
但是题解的离线bfs做法没写特判却过了您的hack数据
by Pecuria @ 2021-06-15 16:34:44
话说这种广义SAM是不是就能解决基排的bug了啊。。。
by Prean @ 2021-06-15 16:35:56