与回文串个数没啥关系啊，就是正常的 SAM 上匹配后缀啊，复杂度没看出来哪里有问题欸。
by 约瑟夫用脑玩 @ 2022-02-16 23:13:35
请具体指出你觉得复杂度有问题的部分，比如第一篇题解代码实现中的“a~b行”。
反正我看上去每一部分都没有问题。
by 约瑟夫用脑玩 @ 2022-02-16 23:14:51
@[约瑟夫用脑玩](/user/158948)
我不太清楚的是 SAM 上匹配后缀的复杂度 /kk
by Godzilla @ 2022-02-17 08:20:59
@[Godzilla](/user/147441) 不只是后缀匹配，SAM 上不管匹配什么，只要匹配 $T$ 个字符复杂度就是 $O(T)$ 的。
因为每次新匹配一个字符长度至多加 $1$，总长度最多 $T$，而跳 parent 链长度至少减 $1$，故至多跳 $T$ 次。
这复杂度的证明不比 SAM 本身的势能证明简单多了/lh
by 约瑟夫用脑玩 @ 2022-02-17 12:30:35
@[约瑟夫用脑玩](/user/158948)
不好意思，我没说清楚，应该是第 71-81 行不太理解，也就是每次匹配就从 maxpos 跳 fa 的过程，这里 now 并不会减小。
```
if(st[now].maxpos<i+l){
if(i<=st[now].maxpos)
ans=max(ans,(ll)(st[now].maxpos-i+1)*dp[now]);
for(int p=st[now].link;p!=-1&&!vis[p];p=st[p].link){
vis[p]=true;
if(i<=st[p].maxpos&&st[p].maxpos<=i+st[p].len-1)
ans=max(ans,(ll)(st[p].maxpos-i+1)*dp[p]);
}
}
```
by Godzilla @ 2022-02-17 12:49:31
@[Godzilla](/user/147441) 是指的这里的 `p` 吗？这里有 `vis` 数组只会访问 $n$ 次啊。
by 约瑟夫用脑玩 @ 2022-02-17 15:02:39
@[约瑟夫用脑玩](/user/158948)
是我眼瞎了，谢谢大佬
by Godzilla @ 2022-02-17 15:05:43