BZOJ2434 阿狸的打字机
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现，这个打字机是这样工作的： ·输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 ·按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。 ·按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。 例如，阿狸输入aPaPBbP，纸上被打印的字符如下： a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。 阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？Input
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。 第二行包含一个整数m，表示询问个数。 接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。 Output 输出m行，其中第i行包含一个整数，表示第i个询问的答案。Sample Input
aPaPBbP 3 1 2 1 3 2 3 Sample Output 2 1 0Hint
1<=N<=10^5 1<=M<=10^5 输入总长<=10^5
标签：AC自动机 Fail树 树状数组
这道题的提示还是很明显的。
读完题目，很容易发现此题打字的部分就是在建一棵Trie树。 输入小写字母即在Trie中添加一个子结点并向儿子结点走，输入‘B'即退回到父结点，输入’P‘即在当前结点打标记。 因而我们可以构建Trie树如下：void init() { //我写Trie树的习惯：把根节点定为1 cnt = 0, root = 1, fa[root] = 0; //0号节点所有儿子都练到根，这样AC自动机CalcFail时更方便 for (int i = 0; i < 26; i++) trie[0][i] = root;}void build() { init(); n = strlen(s); ind = 1;//ind记录当前结点数 for (int i = 0, cur = root; i < n; i++) { if (s[i] == 'B') { //退到父结点 cur = fa[cur]; } else if (s[i] == 'P') { //打标记，标记为第cnt个字符串 pos[++cnt] = cur; } else { //新建子结点 trie[cur][s[i]-'a'] = ++ind; fa[ind] =cur, cur = ind;` }。。 }} 接下来我们对付这题的询问。
首先，它要求一个字符串在另一个字符串中出现多少次，这显然是AC自动机的操作，所以我们建立fail数组如下：void CalcFail() { queue que; que.push(root); while (!que.empty()) { int u = que.front(); for (int i = 0; i < DICNUM; i++) { if (trie[u][i]) { fail[trie[u][i]] = trie[fail[u]][i]; que.push(trie[u][i]); } else { trie[u][i] = trie[fail[u]][i]; } } que.pop(); }} 现在我们考虑fail数组的实质。如果A结点的fail指向B结点，则B结点代表的字符串一定是A结点代表字符串的后缀，即经过A的所有路径组成的字符串都包含B结点代表的字符串。对于一个字符串，它的所有字串为它所有前缀的所有后缀，所以对于询问(x,y)，我们需要找出从根节点到y的路径中有多少结点可以通过fail指针转移到x。
这时我们就需要考虑Fail树了。对于任意结点p，我们把所有通过fail指针能直接转移到p的结点作为p的子结点，而p通过fail指针转移到的结点作为p的父结点。这样我们就能构建一棵树。这样一来，对于询问(x,y)，问题等价于从根到y的结点中有多少节点是在x的子树中。我们就可以用DFS序操作。然后用树状数组维护（线段树太麻烦）。 为了使询问变得更好操作，我们考虑把询问按y值排序，这样我们就只需一直往下走，然后标记经过的结点，然后统计x子树即可。最后附上AC代码：
#include#include #include #include #include #include #define MAX_N 100000#define DICNUM 26using namespace std;int n, m, cnt, ind;int root, trie[MAX_N+5][DICNUM], fa[MAX_N+5], fail[MAX_N+5], pos[MAX_N+5], ans[MAX_N+5];char s[MAX_N+5];vector G[MAX_N+5];int into[MAX_N+5], outo[MAX_N+5];int tr[MAX_N+5];struct Query {int x, y, id;} q[MAX_N+5];bool cmp (const Query &a, const Query &b) {return a.y < b.y;}void init() { cnt = 0, root = 1, fa[root] = 0; for (int i = 0; i < DICNUM; i++) trie[0][i] = root;}void CalcFail() { queue que; que.push(root); while (!que.empty()) { int u = que.front(); for (int i = 0; i < DICNUM; i++) { if (trie[u][i]) { fail[trie[u][i]] = trie[fail[u]][i]; que.push(trie[u][i]); } else { trie[u][i] = trie[fail[u]][i]; } } que.pop(); }}void DFS(int u) { into[u] = ++ind; for (int i = 0; i < G[u].size(); i++) DFS(G[u][i]); outo[u] = ind;}void build() { init(); n = strlen(s); ind = 1; for (int i = 0, cur = root; i < n; i++) { if (s[i] == 'B') { cur = fa[cur]; } else if (s[i] == 'P') { pos[++cnt] = cur; } else { trie[cur][s[i]-'a'] = ++ind; fa[ind] = cur, cur = ind; } } CalcFail(); for (int i = 1; i <= ind; i++) G[fail[i]].push_back(i); ind = 0; DFS(root);}void inc(int pos) {for (; pos <= ind; pos += pos&(-pos)) tr[pos]++;}void dec(int pos) {for (; pos <= ind; pos += pos&(-pos)) tr[pos]--;}int sum(int pos) {int ret = 0; for (; pos; pos -= pos&(-pos)) ret += tr[pos]; return ret;}void solve() { sort(q, q+m, cmp); for (int i = 0, j = 0, cur = root, now = 0; i < n; i++) if (s[i] == 'B') { dec(into[cur]); cur = fa[cur]; } else if (s[i] == 'P') { now++; for (; j < m && q[j].y == now; j++) ans[q[j].id] = sum(outo[pos[q[j].x]])-sum(into[pos[q[j].x]]-1); } else { cur = trie[cur][s[i]-'a']; inc(into[cur]); }}int main() { scanf("%s", s); build(); scanf("%d", &m); for (int i = 0; i < m; i++) scanf("%d%d", &q[i].x, &q[i].y), q[i].id = i; solve(); for (int i = 0; i < m; i++) printf("%d\n", ans[i]); return 0;}