11519: 【原1519】杰瑞的打字机

题目描述

author: 徐亦飞原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1519

Description

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.

a
aa
ab

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)

Input Format

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.

Output Format

m rows, each row is a number, the answer of i-th inquiry.

Sample Input

aPaPBbP
3
1 2
1 3
2 3

Sample Output

2
1
0

Limits

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

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！