【Hackerrank University2】【JZOJ5008】Querying Sums on Strings 题解

题目大意

  $n,~m,~k,~q~<=~1e5$
  $\sum |w|<=1e5$
  1s， 512M

题解

  这题的关键是要抓住“$\sum |w|<=1e5$”这个条件。

  于是我们分 $k<=\sqrt{1e5}$ 和 $k>\sqrt{1e5}$ 两种情况来做。

  当 $k<=\sqrt{1e5}$ 时：
  我们暴力枚举每个 $w$ 的每一个子串，然后求出该子串在 $s$ 中的出现次数，再看该子串被询问了多少次（这个可以预处理+二分什么的乱搞）。

  当 $k>\sqrt{1e5}$ 时：
  此时的 $q<=\sqrt{1e5}$，因此直接求出每个询问子串的出现次数即可。

  求一个串在 $s$ 中的出现次数可以用 SA 或 SAM。