专栏首页数据结构与算法BZOJ2434: [Noi2011]阿狸的打字机(AC自动机 树状数组)

BZOJ2434: [Noi2011]阿狸的打字机(AC自动机 树状数组)

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 4140  Solved: 2276

[Submit][Status][Discuss]

Description

 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。 经阿狸研究发现,这个打字机是这样工作的: l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 l 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。 l 按一下印有'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 0

HINT

 1<=N<=10^5

1<=M<=10^5

输入总长<=10^5

Source

Trie

非常不错的一道题目

首先暴力把每个字符串扔到trie树里并打上标记,$O(M)$

我们查询的是第$x$个字符串在第$y$个字符串中出现了多少次,如果一次一次的查肯定是太浪费了。

考虑能不能一次多查几个,如果你做过这道题的话肯定能想到是AC自动机。

这样我们对于相同的$y$,仅做一次查询就行了。为了更方便的查找,我们对$y$进行排序,这样就可以$O(1)$的维护出$y$的形态

回到上一个问题,考虑如何查询出现次数,

根据$fail$树的性质,我们不难发现,若$x$节点在$root$到$y$任意一个节点的$fail$树上,那么$x$一定就是$y$的子串

(这里简单证明一下:判断一个串是否是另一个串的子串可以转换为判断这个串是否是另一个串前缀后缀,我们枚举从根到$y$的路径,实际上就是枚举了$y$的前缀,而在$fail$树上查找,实际上就是在枚举$y$的后缀)

这样查询一次的复杂度为$O(siz)$,若所有的$y$全不相同肯定还是会凉凉

接下来就是神仙操作了!

考虑转化问题,

若$x$节点在$root$到$y$任意一个节点的$fail$树上,那么$x$一定就是$y$的子串

同理,若$y$在$x$的子树中,那么$x$一定是$y$的子串

这样我们在枚举$y$的时候,可以在经过的路径上打上$+1$的标记(退出的时候打上$-1$的标记),当遇到当前节点为$y$时,查询一下$x$的子树的和就好了

这样的复杂度仍然没有降下来为,$O(siz^2)$

但是!别忘了在树上有一种经典的操作—>dfs序+树状数组

然后这题就$O(siz \log siz)$的做完了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
const int root = 0, B = 26;
int Num, N;
char s[MAXN];
struct Query {
    int x, y, ID, ans;
    bool operator < (const Query &rhs) const {
    return y == rhs.y ? x < rhs.x : y < rhs.y;
    }
}Q[MAXN];
vector<int> v[MAXN];
int ch[MAXN][26], fa[MAXN], fail[MAXN], val[MAXN], siz[MAXN], tot = 0, Pos[MAXN], meiyong = 0;
void Build() {
    int now = root;
    for(int i = 1; i <= N; i++) {
        int x = s[i] - 'a';
        if(x == -31) {now = fa[now]; continue;}
        if(x == -17) {Pos[++meiyong] = now; continue;}
        if(!ch[now][x]) ch[now][x] = ++tot;
        fa[ch[now][x]] = now; now = ch[now][x]; 
    } 
}
void GetFail() {
    queue<int> q; 
    for(int i = 0; i < B; i++) if(ch[root][i]) q.push(ch[root][i]);
    while(!q.empty()) {
        int p = q.front(); q.pop();
        for(int i = 0; i < B; i++)
            if(!ch[p][i]) ch[p][i] = ch[fail[p]][i];
            else fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]);
        v[fail[p]].push_back(p);
    }
}
int ID[MAXN], cnt; //ID[i]表示第i个节点在fail树上的编号 
void dfs(int x) {
    ID[x] = ++cnt; siz[ID[x]] = 1;
    for(int i = 0; i < v[x].size(); i++)
        dfs(v[x][i]), siz[ID[x]] += siz[ID[v[x][i]]];
}
struct BIT {
    #define lb(x) (x & (-x))
    int Tree[MAXN];
    int add(int pos, int val) {
        for(int i = pos; i <= cnt; i += lb(i)) 
        Tree[i] += val;
    }
    int sum(int pos) {
        int ans = 0; 
        for(int i = pos; i >= 1; i -= lb(i)) 
            ans += Tree[i]; 
        return ans; 
    }
    int QUERY(int x, int y) {
        return sum(y) - sum(x - 1);
    }
}T;
void Solve() {
    int now = root, cur = 1, world = 0;
    for(int i = 1; i <= N; i++) {
        int x = s[i] - 'a';
        if(x == -31) {T.add(ID[now], -1), now = fa[now]; continue;}
        else if(x == -17) {
            world++;
            for(int x; Q[cur].y == world; cur++)     
                x = Pos[Q[cur].x], Q[cur].ans = T.QUERY(ID[x], ID[x] + siz[ID[x]] - 1);
        } 
        else now = ch[now][x], T.add(ID[now], +1);
    }
}
bool comp(const Query &a, const Query &b) {
    return a.ID < b.ID;    
}
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
#endif
    scanf("%s", s + 1); N = strlen(s + 1);
    Build();
    GetFail();
    dfs(root);
    Num = read();
    for(int i = 1; i <= Num; i++) {
        int x = read(), y = read();
        Q[i] = (Query) {x, y, i};
    }
    sort(Q + 1, Q + Num + 1);
    Solve();
    sort(Q + 1, Q + Num + 1, comp);
    for(int i = 1; i <= Num; i++)
        printf("%d\n", Q[i].ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P3808 【模版】AC自动机(简单版)

    题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

    attack
  • 洛谷P4197 Peaks(Kruskal重构树 主席树)

    考虑把Kruskal重构树建出来,重构树上每个新的节点代表的是边权,同时用倍增数组维护出跳2^i步后能走到的值最大的节点

    attack
  • BZOJ3509: [CodeChef] COUNTARI(生成函数 分块)

    发现 ,那么有一种暴力思路是枚举j,对于之前出现过的数构造一个生成函数,对于之后出现过的数构造一个生成函数,求一下第 项的值。复杂度

    attack
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

    那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

    用户7727433
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • 网易校招真题三

    题目描述 又到了丰收的季节,恰逢小易去牛牛的果园里游玩。 牛牛常说他对整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛。 在果园里有N堆苹果,...

    黑白格
  • 风险度量

    题目 X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。 两个空间站间可能直接通信,也可能通过其它空间站中转。

    用户4492257
  • L3-004. 肿瘤诊断

    在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。

    指点
  • 滴滴2016.09.06校招 在线笔试 - 2道编程题

    一个数组有N个元素,求连续子数组的最大和。例如:[-1,2,1],和最大的连续子数组为[2,1],其和为3。

    Enjoy233
  • 神奇的 ViewDragHelper,让你轻松定制拥有拖拽能力的 ViewGroup

    相信这种效果大家都见过吧?我第一次见到这样的效果时,心里也痒痒的,急于想实现这种功能,后来因为拖延症的问题,就一直没有去弄这件事。现在这段时间,工作比较轻...

    Frank909

扫码关注云+社区

领取腾讯云代金券