#P2353. 背单词

背单词

题目背景

小明对英语一窍不通,令老师十分头疼。于是期末考试前夕,小明被逼着开始背单词……

题目描述

老师给了小明一篇长度为N的英语文章,然后让小明背M个单词。为了确保小明不会在背单词时睡着,老师会向他提Q个问题,每次老师随机选择一个区间L..R,小明要回答在这段文字中他背过的单词总共出现过多少次。

输入格式

第一行两个整数M、Q如前所述。第二行为英语文章。接下来M行每行一个需要背的单词。接下来Q行每行一个询问,包含两个整数L、R(含端点),即给定的文字区间。

输出格式

Q行,对每个询问输出一行表示答案。

3 3
abcabcbc
abc
bc
a
1 3
6 7
1 8
3
0
7

提示

数据范围:

对于30%的数据,1<=N<=10^3,1<=Q<=10^3

对于60%的数据,1<=N<=10^5,1<=Q<=10^5

对于100%的数据,1<=N<=10^6,1<=M<=10,1<=Q<=10^6,1<=每个单词的长度<=N,1<=L<=R<=N

提示:数据较大,请大家尽量采取高效率的读入输出方法。