由于后缀自动机的构造本来就是一个在线的过程,所以我们可以考虑每次往答案中添加新的贡献。
又根据后缀自动机的定义,不同子串的个数其实就是 tot∑i=1leni−lenfai。
所以我们再每次添加字符的时候更新答案即可。
这题如果用 SA 来做的话会很麻烦,但是 SAM 就很简洁了。
代码:
1 |
|
由于后缀自动机的构造本来就是一个在线的过程,所以我们可以考虑每次往答案中添加新的贡献。
又根据后缀自动机的定义,不同子串的个数其实就是 tot∑i=1leni−lenfai。
所以我们再每次添加字符的时候更新答案即可。
这题如果用 SA 来做的话会很麻烦,但是 SAM 就很简洁了。
代码:
1 | #include <cstdio> |