Problem
给定一个长度为 \(S\) 字符串 \(s\) 与 一个正整数 \(q\)，接下来有 \(q\) 次询问，第 \(i\) 次询问给出一个长度为 \(T_i\) 字符串 \(t_i\)，求 \(t_i\) 在 \(s\) 的出现次数。
保证 \(S,q,\sum^q_{i=1}T_i\leq10^5\)。
Solution
后缀自动机，但是我不会。
注意到 \(\sum^q_{i=1}T_i\leq10^5\)，则 \(T_i\) 的种类至多有 \(\sqrt{10^5}\approx 316\) 种，那么就可以对每一种长度相等的 \(t\) 一起处理，可以使用 Hash 在 \(O(n)\) 的时间复杂度进行计算。这样时间复杂度就是 \(O(n\sqrt{n})\) 的。