Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!