注意到(qk leq 10^5)，我们很不自然地考虑根号分治：
当(k > sqrt{10^5})，此时(q)比较小，与(qm)相关的算法比较适合。对串(s)建SAM，考虑每组询问，将其所有的((a,b))按照(b)从小到大排序，然后把(w)在(s)的SAM上匹配，每当右端点变为(b)的时候倍增跳到串(s[a:b])的位置查询endpos即可。
当(q > sqrt{10^5})，此时(k)比较小，与(k^2)相关的算法比较适合。同样对串(s)建SAM，枚举左端点(l)然后将(w[l:])在SAM上匹配计算出所有的((l,r))的答案，然后对于所有的((l,r))二分求出当前的询问中有多少是当前询问，就可以得到答案。
复杂度(O(msqrt{qk}logn))。一个神奇的事情是块大小(316)过不去但是(315)可以过。