卡常的出题人什么时候似啊？
如果 \(l=1,r=|t|\)，那么就是蠢得不能再蠢的问题：直接扔到 AC 自动机上跑匹配就好了，可以做到 \(O(\sum|s|+|t|)\)。
现在询问的变成了一个子区间，怎么办呢？
一个显然错误的想法就是记 \(pre_i\) 表示 \(t[1,i]\) 中所有字符串出现的次数之和，答案为 \(pre_y-pre_{x-1}\)，这算多了左端点在 \([1,l-1]\) ，右端点在 \([l,r]\) 的情况。
为了把这种情况减掉，我们对所有 \(s\) 的反串建立另一个 AC 自动机，那么形如上面的串应该满足有一个点 \(i\in [1,|s_i|-1]\)，满足 \(s[1,i]\) 在正串的 AC 自动机上是 \([1,l-1]\) 前缀的祖先，\(s[i+1,|s_i|]\) 在反串的 AC 自动机上是 \([l,r]\) 的祖先。这是容易处理的，离线询问以后按照反串的 AC 自动机的 fail 树 dfs ，然后支持子树加，单点查即可。时间复杂度 \(O(|t_i|+(\sum\limits{s_i}+q)\log n)\)。
标签：pre,AC,task,CF1801G,sum,substrings,反串,自动机 From： https://www.cnblogs.com/275307894a/p/17234231.html