//NOI2011(BZOJ2434); 阿狸的打字机; AC Automation - Fail Tree & Binary Indexed Tree
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define N 100000
struct edge
{
int next, node;
};
struct map
{
int head[N + 1], tot;
edge e[N + 1];
map() { tot = 0; }
inline void addedge(int x, int y)
{
e[++tot].next = head[x];
e[tot].node = y;
head[x] = tot;
}
}fail, queries;
//Forward stars, one for fail pointer tree and one for queries
const int root = 1;
struct node
{
int f, son[26], fail;
}t[N + 1];
//Trie tree
char s[N + 1];
//Entry string
int len, tot = root, strs = 0, m;
int strNode[N + 1];
//Corresponding trie node for a string
int queue[N + 1];
int head[N + 1], tail[N + 1], count = 0;
//DFS sequence
int arr[N + 1];
//Binary indexed tree, storing how many nodes of string y are in a certain node and its subtrees
int ans[N + 1];
//Stores the answer to each of the queries
inline int query(int x)
{
int ret = 0;
for (; x; x -= x & (-x))
ret += arr[x];
return ret;
}
inline void modify(int x, int d)
{
for (; x <= count; x += x & (-x))
arr[x] += d;
}
void dfs(int x)
{
head[x] = ++count;
for (int i = fail.head[x]; i; i = fail.e[i].next)
dfs(fail.e[i].node);
tail[x] = count;
}
int main()
{
gets(s);
len = strlen(s);
int now = root;
//Read queries and build queries graph
scanf("%d", &m);
for (int x, y, i = 0; i < m; ++i)
{
scanf("%d%d", &x, &y);
queries.addedge(y, x);
}
//Build trie tree
for (int i = 0; i < len; ++i)
{
if (s[i] == 'P') strNode[++strs] = now;
else if (s[i] == 'B') now = t[now].f;
else
{
if (t[now].son[s[i] - 'a']) now = t[now].son[s[i] - 'a'];
else
{
int cur = now;
t[now = t[now].son[s[i] - 'a'] = ++tot].f = cur;
}
}
}
//Construct fail pointers and build fail pointer tree
int l = 0, r = -1;
for (int i = 0; i < 26; ++i)
{
if (t[root].son[i])
{
queue[++r] = t[root].son[i];
fail.addedge(root, queue[r]);
t[queue[r]].fail = root;
}
}
for (; l <= r; ++l)
{
for (int i = 0; i < 26; ++i)
if (t[queue[l]].son[i])
{
queue[++r] = t[queue[l]].son[i];
for (now = t[queue[l]].fail; now != root && !t[now].son[i]; now = t[now].fail) ;
t[queue[r]].fail = t[now].son[i] ? t[now].son[i] : root;
fail.addedge(t[queue[r]].fail, queue[r]);
}
}
//Construct DFS sequence of fail pointer tree
dfs(root);
//Traverse through trie tree while enumerating y string
now = root, strs = 0;
for (int qs, i = 0; i < len; ++i)
{
if (s[i] == 'B')
{
modify(head[now], -1);
now = t[now].f;
}
else if (s[i] != 'P')
{
now = t[now].son[s[i] - 'a'];
modify(head[now], 1);
}
else
{
for (int x = queries.head[++strs]; x; x = queries.e[x].next)
ans[x] = query(tail[strNode[queries.e[x].node]]) - query(head[strNode[queries.e[x].node]] - 1);
}
}
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
return 0;
}
Ly9OT0kyMDExKEJaT0oyNDM0KTsg6Zi/54u455qE5omT5a2X5py6OyBBQyBBdXRvbWF0aW9uIC0gRmFpbCBUcmVlICYgQmluYXJ5IEluZGV4ZWQgVHJlZQojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGNzdHJpbmc+CiNkZWZpbmUgTiAxMDAwMDAKIApzdHJ1Y3QgZWRnZQp7CiAgICBpbnQgbmV4dCwgbm9kZTsKfTsKc3RydWN0IG1hcAp7CiAgICBpbnQgaGVhZFtOICsgMV0sIHRvdDsKICAgIGVkZ2UgZVtOICsgMV07CiAgICBtYXAoKSB7IHRvdCA9IDA7IH0KICAgIGlubGluZSB2b2lkIGFkZGVkZ2UoaW50IHgsIGludCB5KQogICAgewogICAgICAgIGVbKyt0b3RdLm5leHQgPSBoZWFkW3hdOwogICAgICAgIGVbdG90XS5ub2RlID0geTsKICAgICAgICBoZWFkW3hdID0gdG90OwogICAgfQp9ZmFpbCwgcXVlcmllczsKLy9Gb3J3YXJkIHN0YXJzLCBvbmUgZm9yIGZhaWwgcG9pbnRlciB0cmVlIGFuZCBvbmUgZm9yIHF1ZXJpZXMKY29uc3QgaW50IHJvb3QgPSAxOwpzdHJ1Y3Qgbm9kZQp7CiAgICBpbnQgZiwgc29uWzI2XSwgZmFpbDsKfXRbTiArIDFdOwovL1RyaWUgdHJlZQpjaGFyIHNbTiArIDFdOwovL0VudHJ5IHN0cmluZwppbnQgbGVuLCB0b3QgPSByb290LCBzdHJzID0gMCwgbTsKaW50IHN0ck5vZGVbTiArIDFdOwovL0NvcnJlc3BvbmRpbmcgdHJpZSBub2RlIGZvciBhIHN0cmluZwppbnQgcXVldWVbTiArIDFdOwppbnQgaGVhZFtOICsgMV0sIHRhaWxbTiArIDFdLCBjb3VudCA9IDA7Ci8vREZTIHNlcXVlbmNlCmludCBhcnJbTiArIDFdOwovL0JpbmFyeSBpbmRleGVkIHRyZWUsIHN0b3JpbmcgaG93IG1hbnkgbm9kZXMgb2Ygc3RyaW5nIHkgYXJlIGluIGEgY2VydGFpbiBub2RlIGFuZCBpdHMgc3VidHJlZXMKaW50IGFuc1tOICsgMV07Ci8vU3RvcmVzIHRoZSBhbnN3ZXIgdG8gZWFjaCBvZiB0aGUgcXVlcmllcwogCmlubGluZSBpbnQgcXVlcnkoaW50IHgpCnsKICAgIGludCByZXQgPSAwOwogICAgZm9yICg7IHg7IHggLT0geCAmICgteCkpCiAgICAgICAgcmV0ICs9IGFyclt4XTsKICAgIHJldHVybiByZXQ7Cn0KIAppbmxpbmUgdm9pZCBtb2RpZnkoaW50IHgsIGludCBkKQp7CiAgICBmb3IgKDsgeCA8PSBjb3VudDsgeCArPSB4ICYgKC14KSkKICAgICAgICBhcnJbeF0gKz0gZDsKfQogCnZvaWQgZGZzKGludCB4KQp7CiAgICBoZWFkW3hdID0gKytjb3VudDsKICAgIGZvciAoaW50IGkgPSBmYWlsLmhlYWRbeF07IGk7IGkgPSBmYWlsLmVbaV0ubmV4dCkKICAgICAgICBkZnMoZmFpbC5lW2ldLm5vZGUpOwogICAgdGFpbFt4XSA9IGNvdW50Owp9CiAKaW50IG1haW4oKQp7CiAgICBnZXRzKHMpOwogICAgbGVuID0gc3RybGVuKHMpOwogICAgaW50IG5vdyA9IHJvb3Q7CiAgICAvL1JlYWQgcXVlcmllcyBhbmQgYnVpbGQgcXVlcmllcyBncmFwaAogICAgc2NhbmYoIiVkIiwgJm0pOwogICAgZm9yIChpbnQgeCwgeSwgaSA9IDA7IGkgPCBtOyArK2kpCiAgICB7CiAgICAgICAgc2NhbmYoIiVkJWQiLCAmeCwgJnkpOwogICAgICAgIHF1ZXJpZXMuYWRkZWRnZSh5LCB4KTsKICAgIH0KICAgIC8vQnVpbGQgdHJpZSB0cmVlCiAgICBmb3IgKGludCBpID0gMDsgaSA8IGxlbjsgKytpKQogICAgewogICAgICAgIGlmIChzW2ldID09ICdQJykgc3RyTm9kZVsrK3N0cnNdID0gbm93OwogICAgICAgIGVsc2UgaWYgKHNbaV0gPT0gJ0InKSBub3cgPSB0W25vd10uZjsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBpZiAodFtub3ddLnNvbltzW2ldIC0gJ2EnXSkgbm93ID0gdFtub3ddLnNvbltzW2ldIC0gJ2EnXTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgY3VyID0gbm93OwogICAgICAgICAgICAgICAgdFtub3cgPSB0W25vd10uc29uW3NbaV0gLSAnYSddID0gKyt0b3RdLmYgPSBjdXI7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICAvL0NvbnN0cnVjdCBmYWlsIHBvaW50ZXJzIGFuZCBidWlsZCBmYWlsIHBvaW50ZXIgdHJlZQogICAgaW50IGwgPSAwLCByID0gLTE7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDI2OyArK2kpCiAgICB7CiAgICAgICAgaWYgKHRbcm9vdF0uc29uW2ldKQogICAgICAgIHsKICAgICAgICAgICAgcXVldWVbKytyXSA9IHRbcm9vdF0uc29uW2ldOwogICAgICAgICAgICBmYWlsLmFkZGVkZ2Uocm9vdCwgcXVldWVbcl0pOwogICAgICAgICAgICB0W3F1ZXVlW3JdXS5mYWlsID0gcm9vdDsKICAgICAgICB9CiAgICB9CiAgICBmb3IgKDsgbCA8PSByOyArK2wpCiAgICB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyNjsgKytpKQogICAgICAgICAgICBpZiAodFtxdWV1ZVtsXV0uc29uW2ldKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBxdWV1ZVsrK3JdID0gdFtxdWV1ZVtsXV0uc29uW2ldOwogICAgICAgICAgICAgICAgZm9yIChub3cgPSB0W3F1ZXVlW2xdXS5mYWlsOyBub3cgIT0gcm9vdCAmJiAhdFtub3ddLnNvbltpXTsgbm93ID0gdFtub3ddLmZhaWwpIDsKICAgICAgICAgICAgICAgIHRbcXVldWVbcl1dLmZhaWwgPSB0W25vd10uc29uW2ldID8gdFtub3ddLnNvbltpXSA6IHJvb3Q7CiAgICAgICAgICAgICAgICBmYWlsLmFkZGVkZ2UodFtxdWV1ZVtyXV0uZmFpbCwgcXVldWVbcl0pOwogICAgICAgICAgICB9CiAgICB9CiAgICAvL0NvbnN0cnVjdCBERlMgc2VxdWVuY2Ugb2YgZmFpbCBwb2ludGVyIHRyZWUKICAgIGRmcyhyb290KTsKICAgIC8vVHJhdmVyc2UgdGhyb3VnaCB0cmllIHRyZWUgd2hpbGUgZW51bWVyYXRpbmcgeSBzdHJpbmcKICAgIG5vdyA9IHJvb3QsIHN0cnMgPSAwOwogICAgZm9yIChpbnQgcXMsIGkgPSAwOyBpIDwgbGVuOyArK2kpCiAgICB7CiAgICAgICAgaWYgKHNbaV0gPT0gJ0InKQogICAgICAgIHsKICAgICAgICAgICAgbW9kaWZ5KGhlYWRbbm93XSwgLTEpOwogICAgICAgICAgICBub3cgPSB0W25vd10uZjsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZiAoc1tpXSAhPSAnUCcpCiAgICAgICAgewogICAgICAgICAgICBub3cgPSB0W25vd10uc29uW3NbaV0gLSAnYSddOwogICAgICAgICAgICBtb2RpZnkoaGVhZFtub3ddLCAxKTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgZm9yIChpbnQgeCA9IHF1ZXJpZXMuaGVhZFsrK3N0cnNdOyB4OyB4ID0gcXVlcmllcy5lW3hdLm5leHQpCiAgICAgICAgICAgICAgICBhbnNbeF0gPSBxdWVyeSh0YWlsW3N0ck5vZGVbcXVlcmllcy5lW3hdLm5vZGVdXSkgLSBxdWVyeShoZWFkW3N0ck5vZGVbcXVlcmllcy5lW3hdLm5vZGVdXSAtIDEpOwogICAgICAgIH0KICAgIH0KICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG07ICsraSkKICAgICAgICBwcmludGYoIiVkXG4iLCBhbnNbaV0pOwogICAgcmV0dXJuIDA7Cn0K