大视线 2434 阿狸的打字机 【字符串_AC自动机】【NOI 2011】

大视野 2434 阿狸的打字机 【字符串_AC自动机】【NOI 2011】

题目链接: http://61.187.179.132/JudgeOnline/problem.php?id=2434

题目大意: 给定一个长串，可以解析成n个串，m个询问，每个询问为一对(x,y)，询问串y包含几个串x，n、m、串总长度<=10万。

解题思路: 神一样的NOI题目，好题，因为不会做(哈哈，这是前段时间听到很恶搞的好题逻辑)。就因为这题我学习了树状数组，学习了fail树。这题代码量相当大，如果用线段树的话估计得上300行，调试起来会蛋疼菊紧，所以就去学了轻巧的树状数组，像这种区间求和的问题，用树状数组解决最漂亮了。

    貌似本题有两种解法，后缀数组和AC自动机，我实现的AC自动机版本就谈谈AC自动机是如何解本题的。

    一开始，我用的是比较暴力的写法，建好AC自动机，然后在线去查询，查询的时候每碰到一个字符就顺着fail指针往前查找到root。但这样写，果断TLE，很彻底的暴力方法。然后改造改成离线查询，每次查询y对应的多个x，这个只要往前找的时候统计多个就好，仍然TLE,但据搞NOI的的人称这样可以骗到70分。其实noi那种模式还是很有意思，两次去福大参加校赛都用乱七八糟的算法各种骗分...

     TLE无果，便去问同校的大牛，他只说了一句很轻松的话--很简单的fail树+树状数组,汗...据他说，fail树就是把fail指针反转后重新建的树，这样查询(x,y)，y会出现在x的子树中。描述地略微蛋疼，便去百度找了解题报告。看了几篇报告后大概地明白其中的核心思想。

     先研究下查询对(x,y)，如果串x出现在串y中，那么串y有几个前缀的后缀以串x结尾，便是出现的次数，简单地说串y从某个位置顺着fail指针能到达串x尾就增加一次。这是多对一的关系，换个角度想，如果是一对多的话会容易解决些，从串x的末尾逆着刚刚从串y来的fail指针能到达几个y中位置，那么就有几次。

     上面那步很容易转换，但关键问题是如果逆这刚刚从串y来的指针走呢？逆着fail指针重新建树！这就是fail树了。当我们构建好了fail树之后，要做的就是查询x的子树中有几个节点属于串y。当我们对fail树进行dfs，dfs到某个节点的时候将顺序记为first,退出的时候记为end,如1,2,3,x ... x 3 2 1,x和x之间的数便都是x的子孙节点。接着我们进行区间查询，查询x和x之间有几个属于y的结点。

     把上面的处理都搞定了之后，就是如何查询了。我们使用数组C来辅助，初始化为0，然后我们把串y在ac自动机上的结点对应的下标全赋值成1，问题就转变为fist[x]和end[x]里有几个1了，这时使用树状数组来计算区间和。我们采用离线查询，把所有有y的查询存起来，当遇到y的末节点的时候拿出来统一处理。我们顺着建AC自动机时的路线再遍历一遍AC自动机，遇到普通字母对应下标的值赋成1，遇到B减1，遇到P查询。

     然后就顺编码了，这题的编码量巨大，但是写完了之后就很顺利地AC了。

测试数据：

代码：

#include <stdio.h>#include <string.h>#include <map>#include <vector>#include <string>#include <sstream>#include <iostream>#include <algorithm>using namespace std;#define MAXNODE 26#define MAXSIZE 110000struct Querynode{    int x,in;}cur;char str[MAXSIZE];int n,m,len,ans[MAXSIZE];vector<Querynode> query[MAXSIZE];struct BinTree {    int n,C[MAXSIZE*2];    void Initial() {        n = len * 2;        memset(C,0,sizeof(C));    }    int Lowbit(int x) {        return x & (x ^ (x - 1));    }    int Sum(int pos) {        int sum = 0;        while (pos > 0) {            sum += C[pos];            pos -= Lowbit(pos);        }        return sum;    }    void Plus(int pos,int add) {        while (pos <= n) {            C[pos] += add;            pos += Lowbit(pos);        }    }}bintree;struct ACnode {    int flag,in;    ACnode *next[MAXNODE],*fail,*father;};struct Auto_AC {    int ptr, failptr, total, head, tail;    int Index[MAXSIZE], Hash[MAXSIZE];    int cnt,first[MAXSIZE], end[MAXSIZE];    ACnode *p, *q, *root;    ACnode *qu[MAXSIZE], tree[MAXSIZE];    vector<int> failtree[MAXSIZE];    void AddFailEdge(int x,int y) {        failtree[x].push_back(y);    }    ACnode *CreateNode() {        tree[ptr].flag = 1;        tree[ptr].in = ptr;        for (int i = 0; i < MAXNODE; ++i)            tree[ptr].next[i] = NULL;        return &tree[ptr++];    }    void Initial() {        cnt = ptr = total = 0;        root = CreateNode();        root->fail = root;        memset(Hash,0,sizeof(Hash));    }    int GetHash(char c) {        return c - 'a';    }    void Insert(char *str) {        p = root;        for (int i = 0; str[i]; ++i) {            if (str[i] == 'P')                Index[++total] = p->in, Hash[i] = total;            else if (str[i] == 'B')                p = p->father;            else {                int k = GetHash(str[i]);                if (p->next[k] == NULL)                    p->next[k] = CreateNode();                q = p,p = p->next[k];                p->father = q;            }        }    }    void Build_AC() {        qu[head++] = root;        while (tail < head) {            p = qu[tail++];            for (int k = 0; k < MAXNODE; ++k)                if (p->next[k]) {                    if (p == root) p->next[k]->fail = root;                    else p->next[k]->fail = p->fail->next[k];                    qu[head++] = p->next[k];                }                else {                    if (p == root) p->next[k] = root;                    else p->next[k] = p->fail->next[k];                }        }    }    void Build_FailTree() {        for (int i = 1; i <= len; ++i)            failtree[i].clear();        for (int k = 1; k < ptr; ++k)            AddFailEdge(tree[k].fail->in,tree[k].in);    }    void Dfs_ForFailTree(int s) {        first[s] = ++cnt;        int size = failtree[s].size();        for (int i = 0; i < size; ++i)            Dfs_ForFailTree(failtree[s][i]);        end[s] = ++cnt;    }    int Query(char *str) {        p = root,bintree.Initial();        for (int i = 0; str[i]; ++i) {            if (str[i] == 'P') {                int y = Hash[i];                if (y == 0) continue;                for (int k = 0; k < query[y].size(); ++k) {                    cur = query[y][k];                    int x = Index[cur.x],in = cur.in;                    ans[in] = bintree.Sum(end[x]) - bintree.Sum(first[x]-1);                }            }            else if (str[i] == 'B') {                bintree.Plus(first[p->in],-1);                p = p->father;            }            else {                p = p->next[GetHash(str[i])];                bintree.Plus(first[p->in],1);            }        }   }}AC;int main() {    int i, j, k, x, y;    scanf("%s", str);    len = strlen(str);    AC.Initial();    AC.Insert(str);    AC.Build_AC();    for (i = 1; i <= len; ++i)        query[i].clear();    scanf("%d", &m);    for (i = 1; i <= m; ++i) {        scanf("%d%d", &x, &y);        cur.x = x, cur.in = i;        query[y].push_back(cur);    }    AC.Build_FailTree();    AC.Dfs_ForFailTree(0);    AC.Query(str);    for (i = 1; i <= m; ++i)        printf("%d\n", ans[i]);}

本文ZeroClock原创，但可以转载，因为我们是兄弟。