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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1079 回家

1079 回家 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 现在是晚餐...

38111
来自专栏技术沉淀

Ruby练习一=> {'a' => 3, 'man' => 1, 'canal' => 1, 'panama' => 1, 'plan' => 1}returns the list ["Pam", "

1072
来自专栏Clive的技术分享

代码重构的方法

1914
来自专栏码匠的流水账

聊聊storm的ICommitterTridentSpout

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/spout/ICommitterTridentSp...

1113
来自专栏Android知识点总结

看得见的数据结构Android版之双链表篇

671
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(二):基本操作(判断、运算、基本函数)

? 今天开始注重变量操作。 SAS生成新变量 SAS支持基本的加减乘除,值得一提的是它的**代表指数,而不是^。* Modify homegarden dat...

4394
来自专栏Hellovass 的博客

优雅地烘焙 DBService

记得大二那年第一次接触 GreenDao 这个神奇的数据库,惊叹道,哇,原来代码还能这么写啊,不用自己手撸 SQLiteDatabase,不用写那些麻烦的 SQ...

1394
来自专栏移动端开发

iOS RunTime你知道了总得用一下

说点题外话: 我刚来现在这家公司的时候,老板让我下载一个脉脉,上去找找自己的同行,多认识些同行。其实初衷的好的,但最近这两天我把它卸载了,不为别的,负能量太多...

2139
来自专栏数说工作室

统计师的Python日记【第4天:欢迎光临Pandas】

本文是【统计师的Python日记】第4天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型; 第2天学习了python的函数、...

3999
来自专栏码匠的流水账

聊聊storm的JoinBolt

storm-2.0.0/storm-client/src/jvm/org/apache/storm/bolt/JoinBolt.java

1584

扫码关注云+社区

领取腾讯云代金券