阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 28 28 个按键，分别印有 26 26 个小写英文字母和 B、P 两个字母。经阿狸研究发现，这个打字机是这样工作的： 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 按一下印有 B 的按键，打字机凹槽中最后一个字母会消失。 按一下印有 P 的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。 例如，阿狸输入 aPaPBbP，纸上被打印的字符如下： a aa ab 我们把纸上打印出来的字符串从 1 1 开始顺序编号，一直到 � n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 ( � , � ) (x,y)（其中 1 ≤ � , � ≤ � 1≤x,y≤n），打字机会显示第 � x 个打印的字符串在第 � y 个打印的字符串中出现了多少次。 阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？ 输入格式 输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。 第二行包含一个整数 � m，表示询问个数。 接下来 � m 行描述所有由小键盘输入的询问。其中第 � i 行包含两个整数 � , � x,y，表示第 � i 个询问为 ( � , � ) (x,y)。 输出格式 输出 � m 行，其中第 � i 行包含一个整数，表示第 � i 个询问的答案

这道题可以使用字符串和前缀和的思路来解决，具体步骤如下：

1. 读入字符串，用一个数组记录下每个字符串打印后的结果，同时用另一个数组记录下每个字符串的长度。

2. 读入询问个数 m，然后读入 m 行询问，每次查询时先找到第 x 个字符串和第 y 个字符串，然后枚举第一个字符串中的所有子串，判断该子串是否在第二个字符串中出现过。如果出现过，则将答案加 1。

3. 最后输出所有询问的答案。

下面是详细的代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
char str[N];
char s[N][N];
int len[N];
int sum[N][N];

int main()
{
    cin >> str + 1;
    n = strlen(str + 1);

    int cur = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (str[i] == 'B') cur = max(0, cur - 1);
        else if (str[i] == 'P')
        {
            s[++ m][0] = cur;
            for (int j = 1; j <= cur; j ++ ) s[m][j] = s[m][j - 1] + str[i - cur + j];
            len[m] = cur;
        }
        else s[m + 1][++ cur] = str[i];
    }

    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j <= len[i]; j ++ )
            for (int k = 1; k <= m; k ++ )
                for (int l = 0; l <= len[k]; l ++ )
                    if (strncmp(s[i] + j, s[k] + l, len[i] - j + 1) == 0) sum[i][k] ++ ;

    cin >> m;
    while (m -- )
    {
        int x, y;
        cin >> x >> y;
        int res = 0;
        for (int i = 0; i <= len[x]; i ++ )
            for (int j = 1; j <= m; j ++ )
                if (strncmp(s[x] + i, s[j], len[x] - i + 1) == 0) res += sum[j][y];
        cout << res << endl;
    }

    return 0;
}