author: 徐亦飞 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1519
Jerry have an antique typewriter with only 28 keys, which are 26 lowercase letter and two uppercase letter ‘B’ and ‘P’. This typewriter works by the following:
- Press the lowercase letter: Insert this letter to the end of the line.
- Press letter ‘B’ : Delete the last letter in the line.
- Press letter ‘P’ : Print the line. (Notice the line won’t be clean)
For example, Jerry input ‘aPaPBbP’, three ‘P’ are pressed and three line will be printed.
The typewriter has an excited feature that by inputting two number x and y (1<=x,y<=n), the typewriter will output how many times the x-th line string has emerged in the y-th line string. (We number mark the first printed line as 1-st line, etc.)
Let’s stimulate this excited feature!
(From NOI2011 Day1 - Problem 3 Ali's Typewriter) (This is the problem D for SEIEE-Yu Yong Data Structure 2015 Fall Exam 1)
The first row is a string with length L. (Only with the lowercase letter and ‘B’’P’) There will be at most N times ‘P’ in this string and every line being printed is no longer than K.
The second row is a number m, represent the number of inquiry.
The next m rows is the input of the inquiry. There are two number x and y, means the i-th inquiry is asking how many times the x-th line string has emerged in the y-th line string.
m rows, each row is a number, the answer of i-th inquiry.
aPaPBbP 3 1 2 1 3 2 3
2 1 0
- 40% N<100 ; M < 1000 ; K, L < 100
- 60% N<1000 ; M < 10^4 ; K < 1000 ; L < 10^5
- 90% N<10^4
- 100% N<10^5 ; M < 10^5 ; K, L < 10^5