一个串在 SAM 上跑匹配，每次匹配前缀 i 在SAM 上最大后缀复杂度是线性的吗？为什么？

类似这样：

int nw=0;
for(int i=1;i<=n;i++){
  while(!t[nw].nxt[s[i]])nw=t[nw].fa;
  if(t[nw].nxt[s[i]])nw=t[nw].nxt[s[i]];
}