Skip to content

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



author: 徐亦飞 原OJ链接:


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

1 2
1 3
2 3

Sample Output



  • 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! 本题目还没有解答!