题解 P6139 【【模板】广义后缀自动机（广义SAM）】

和[Mital](https://www.luogu.com.cn/user/30036)自己yy的后缀树做法，不知道全网有没有类似做法。~~个人对后缀树的理解并不深入，有问题欢迎在评论区提出，求轻喷~~ 还不会后缀树？安利一波[EternalAlexander](https://www.luogu.com.cn/blog/EternalAlexander/xuan-ku-hou-zhui-shu-mo-shu) 对于每一个字符串，我们根据后缀树一般套路，在其后面补充一个字符集以外的字符。 然后将字符集一个个丢尽后缀树 我们知道，本质不同的子串个数对应到后缀树上就是所有边长度之和。对于每一个叶子节点，他的$len$在后缀树中是视为$\infty$的，这里的处理方式是对每一个字符串记录一个结尾位置，如果是叶子节点，则一定这条边代表$s[start[u], end]$，记录一个$end$即可 想象我们把所有字符集首尾相连，之间用不同的字符集连接，那么这样原本的每一个子串都会包括进来。唯一的影响是跨国特殊字符所组成的后缀，然而这样的字符串一定会由于特殊字符的出现，而单独成一个节点。由于我们记录了$end$，所以这个影响是不存在的 ```cpp il void extend(int x) { ++ pax, ++ rem, last = 1; while(rem) { while(rem > len[ch[now][s[pax - rem + 1]]]) rem -= len[now = ch[now][s[pax - rem + 1]]]; int &v = ch[now][s[pax - rem + 1]], c = s[start[v] + rem - 1]; if(!v || c == x) { link[last] = now, last = now; if(!v) v = newnode(pax, inf), son[now].push_back(s[pax - rem + 1]); else break; } else { int u = newnode(start[v], rem - 1); ch[u][x] = newnode(pax, inf), son[u].push_back(x); ch[u][c] = v, son[u].push_back(c), start[v] += rem - 1, len[v] -= rem - 1; link[last] = v = u, last = u; } if(now == 1) -- rem; else now = link[now]; } if(x > 25) ++ co; } il void dfs(int u, int dep) { ans += e[u] - start[u]; if(dep > inf / 10) return; for(re int i = 0; i < son[u].size(); ++ i) if(ch[u][son[u][i]]) dfs(ch[u][son[u][i]], dep + len[ch[u][son[u][i]]]); } ``` 但是这样字符集太大，还需要用到$map+vector$来处理，常数过大，而且带上$map$的$log$，只能获得$60pts$的好成绩，于是我们来思考这个插入一个不同字符的意义 本质上，我们只需要所有后缀在字符集上出现过即可。设想一下，假设我们插入的字符集全部一样，那么那些地方是不合法的 显然如果一条边跨过了两个字符串（包含了一个特殊字符），那么这个特殊字符以下的点是不能被计算的。我们减掉贡献即可（与普通后缀树只有$dfs$的地方有区别） ```cpp il void dfs(int u, int dep) { if(len[u] <= inf / 10 && lower_bound(End + 1, End + T + 1, start[u]) != lower_bound(End + 1, End + T + 1, start[u] + len[u])) { ans += End[lower_bound(End + 1, End + T + 1, start[u]) - End] - start[u]; return; } ans += e[u] - start[u]; if(dep > inf / 10) return; rep(i, 0, 26) if(ch[u][i]) dfs(ch[u][i], dep + len[ch[u][i]]); } ``` $\rm Mital$还提供了一个思路，大概是每次插入完成一个字符串时，强行讲$now=1, rem=0$。因为我们需要的后缀树形态是只有 每个串 的所有后缀，这样操作可以相当于每次往后缀树丢节点，然后每个字符串互不影响，也就相当于把所有后缀树进行了合并。代码就不贴了，跟普通后缀树几乎一样。