考虑拆开贡献，前缀贡献痕容易算。而跨越 \([l-1,l]\) 的贡献，考虑在正串 ACAM 找到 \([1,l-1]\)，反串 ACAM 找到 \([l,r]\)，那么要做的就是在两串的 fail 链祖先上，找到能凑成完整串的对数。对于每个串，枚举放在正串部分的长度，找到两侧对应的点，将询问挂上去即可。最后离线询问，在反串 ACAM 上 DFS 即可。而点定位，反串需要倍增。正串直接做就行。
其实还有一个做法，就是观察 \([l,r]\) 的匹配过程，将若干次跳 fail 看成移动 \(l\) 。由此可以建一棵树。离线扫描并查集就可以找到 \(l\) 最后到达的位置，贡献是祖先链上一段前缀。于是关键在于求：对每个 \([l,n]\) 找到这个 \(t\) 的后缀从 ACAM 的根开始走，不跳 fail 走到的最后位置。于是用 SA-IS 把 \(t\) 后缀排序，按照后缀的排名在 ACAM 上走即可。复杂度可以做到纯线性，但常数较大。
不对，应该是常数太大了，反正我没跑过去。
标签：task,找到,题解,ACAM,后缀,substrings,反串,fail,正串 From： https://www.cnblogs.com/qiulyqwq/p/17207982.html