AC自动机 hdu2896 hdu3065 病毒侵袭

hdu2896

题意：在文本串中找出所包含的模式串，并计数有多少文本串，具体可看

hdu2896 http://acm.hdu.edu.cn/showproblem.php?pid=2896

知道AC自动机就很好做了

推荐的学习链接:

http://acm.uestc.edu.cn/bbs/read.php?tid=4294

http://blog.csdn.net/niushuai666/article/details/7002823

最好是看刘汝佳的训练指南，感觉更好理解

代码:

//text中出现哪些模式串
#include<cstring>
#include<queue>
#include<cstdio>
#include<map>
#include<string>
#include<algorithm>
#define MT(x,i) memset(x,i,sizeof(x))
using namespace std;
queue<int>q;
int ans[5],cc;
const int MAXNODE = 500*200 +100;
struct ACA
{
    int ch[MAXNODE][130];//点 ASCII码
    int f[MAXNODE]; //fail数组
    int val[MAXNODE]; //>0就是单词位尾节点
    int last[MAXNODE]; //后缀节点
    int sz; //节点总数

    void init(){
        sz=1; //一个根节点
        MT(ch[0],0);
    }

    void Insert(char *s,int v){ //插入字符串。v>0
        int u=0,n=strlen(s);
        for(int i=0;i<n;i++){
            int c=s[i];
            if(!ch[u][c]){ //节点不存在
                MT(ch[sz],0);
                val[sz]=0;
                ch[u][c]=sz++; //新建节点
            }
            u=ch[u][c]; //往下走
        }
        val[u]=v; //单词尾标记信息
    }

    void getFail(){
        while(!q.empty())q.pop();
        f[0]=0;
        for(int c=0;c<128;c++){ //初始化队列
            int u=ch[0][c];
            if(u) {f[u]=0;q.push(u);last[u]=0; }
        }

        //BFS计算失配函数
        while(!q.empty()){
            int r=q.front();q.pop();
            for(int c=0;c<128;c++){
                int u=ch[r][c];
                if(!u) { ch[r][c]=ch[f[r]][c]; continue; }
                q.push(u);
                int v=f[r];
                while(v&&!ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }
    void print(int j){
        if(j) ans[cc++]=val[j]; //存下j号模式串标记
    }
    void Find(char *T){//在text中找模板串
        int n=strlen(T);
        int j=0; //当前节点编号，初始为根节点
        for(int i=0;i<n;i++){
            int c=T[i];
            j=ch[j][c];
            if(val[j]) print(j);
            else if(last[j]) print(last[j]);
        }
    }
};

ACA ac;
char bd[210],web[11000];

int main()
{
    int n,m;
    while(~scanf("%d",&n)){
        ac.init();   int total=0;
        for(int i=1;i<=n;i++){
            scanf("%s",bd);
            ac.Insert(bd,i);
        }
        ac.getFail();
        scanf("%d",&m);
        for(int w=1;w<=m;w++){
            scanf("%s",web);
            cc=0;
            ac.Find(web);
            if(cc>0){
                total++;
                printf("web %d:",w);
                sort(ans,ans+cc);
                for(int i=0;i<cc;i++) printf(" %d",ans[i]);
                puts("");
            }
        }
        printf("total: %d\n",total);
    }
    return 0;
}

hdu 3065 http://acm.hdu.edu.cn/showproblem.php?pid=3065

对每个找到的模式串计数，并没有什么不同

#include<cstring>
#include<queue>
#include<cstdio>
#include<map>
#include<string>
#include<algorithm>
#define MT(x,i) memset(x,i,sizeof(x))
using namespace std;
queue<int>q;
int cnt[1005];
const int MAXNODE = 1000*50 +100;
struct ACA
{
    int ch[MAXNODE][130];//点 ASCII码
    int f[MAXNODE]; //fail数组
    int val[MAXNODE]; //>0就是单词位尾节点
    int last[MAXNODE]; //后缀节点
    int sz; //节点总数

    void init(){
        sz=1; //一个根节点
        MT(ch[0],0);
    }

    void Insert(char *s,int v){ //插入字符串。v>0
        int u=0,n=strlen(s);
        for(int i=0;i<n;i++){
            int c=s[i];
            if(!ch[u][c]){ //节点不存在
                MT(ch[sz],0);
                val[sz]=0;
                ch[u][c]=sz++; //新建节点
            }
            u=ch[u][c]; //往下走
        }
        val[u]=v; //单词尾标记信息
    }

    void getFail(){
        while(!q.empty())q.pop();
        f[0]=0;
        for(int c=0;c<128;c++){ //初始化队列
            int u=ch[0][c];
            if(u) {f[u]=0;q.push(u);last[u]=0; }
        }

        //BFS计算失配函数
        while(!q.empty()){
            int r=q.front();q.pop();
            for(int c=0;c<128;c++){
                int u=ch[r][c];
                if(!u) { ch[r][c]=ch[f[r]][c]; continue; }
                q.push(u);
                int v=f[r];
                while(v&&!ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }
    void print(int j){
        if(j) cnt[val[j]]++; //j号模式串计数+1
    }
    void Find(char *T){//在text中找模板串
        int n=strlen(T);
        int j=0; //当前节点编号，初始为根节点
        for(int i=0;i<n;i++){
            int c=T[i];
            j=ch[j][c];
            if(val[j]) print(j);
            else if(last[j]) print(last[j]);
        }
    }
};

ACA ac;
char bd[1100][55],web[2100000];

int main()
{
    int n,m;
    while(~scanf("%d",&n)){
        ac.init();
        for(int i=1;i<=n;i++){
            scanf("%s",bd[i]);
            ac.Insert(bd[i],i);
        }
        ac.getFail();
        scanf("%s",web);
        MT(cnt,0);
        ac.Find(web);
        for(int i=1;i<=n;i++){
            if(cnt[i]>0)
                printf("%s: %d\n",bd[i],cnt[i]);
        }
    }
    return 0;
}

AC自动机模板：

const int SIGMA_SIZE = 26;
const int MAXNODE = 11000;
const int MAXS = 150 + 10;

map<string,int>ms;

struct AhoCorasickAutomata
{
    int ch[MAXNODE][SIGMA_SIZE];
    int f[MAXNODE];//fail数组
    int val[MAXNODE];//val>0就是单词节点
    int last[MAXNODE];//链表的下一个节点
    int cnt[MAXS];
    int sz;//节点总数

    void init(){
        sz=1;//初始时一个根节点
        memset(ch[0],0,sizeof(ch[0]));
        memset(cnt,0,sizeof(cnt));
        ms.clear();
    }

    int idx(char c){
        return c-'a';
    }

    //插入字符串。v必须非0
    void Insert(char *s,int v){
        int u=0,n=strlen(s);
        for(int i=0;i<n;i++){
            int c=idx(s[i]);
            if(!ch[u][c]){//节点不存在
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;//中间节点是0
                ch[u][c]=sz++;//新建节点
            }
            u=ch[u][c];//往下走
        }
        val[u]=v;//字符串最后一个字符标志信息为v
        ms[string(s)]=v;
    }

    //递归打印以节点j结尾的所有字符串
    void print(int j){
        if(j){
            cnt[val[j]]++;
            print(last[j]);
        }
    }

    //在T中找模板
    int Find(char *T){
        int n = strlen(T);
        int j=0;//初试为根，当前节点编号
        for(int i=0;i<n;i++){ //文本串当前指针
            int c=idx(T[i]);
            while(j&&!ch[j][c]) j=f[j];//顺着失配走，直到可以匹配到
            j=ch[j][c];
            if(val[j]) print(j);
            else if(last[j]) print(last[j]);//找到了
        }
    }

    void getFail(){
        queue<int>q;
        f[0]=0;

        for(int c=0;c<SIGMA_SIZE;c++){//初始化队列
            int u=ch[0][c];
            if(u){
                f[u]=0;q.push(u);last[u]=0;
            }
        }

        while(!q.empty()){
            int r=q.front();q.pop();
            for(int c=0;c<SIGMA_SIZE;c++){
                int u=ch[r][c];
                if(!u) continue;
                q.push(u);
                int v=f[r];
                while(v&&!ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

};

AhoCorasickAutomata ac;
char text[1000005],P[151][80];
int n,T;

int main()
{
    while(scanf("%d", &n) == 1 && n)
    {
        ac.init();
        for(int i=1;i<=n;i++){
            scanf("%s",P[i]);
            ac.Insert(P[i],i);//注意同时更新ms映射
        }
        ac.getFail();
        scanf("%s",text);
        ac.Find(text);//计算每个模板的cnt
        int best = -1;
        for(int i=1;i<=n;i++)
            if(ac.cnt[i]>best) best=ac.cnt[i];//最大值
        printf("%d\n",best);
        for(int i=1;i<=n;i++)
            if(ac.cnt[ms[string(P[i])]]==best) printf("%s\n",P[i]);//输出那些模板串
    }
    return 0;
}

一般的模板题，计数都只需要更改print函数即可

AC自动机 hdu2896 hdu3065 病毒侵袭

继续阅读

CF-346 D. Robot Control(反向建图spfa)

ACMer成长之路

pat（B）1009. 说反话（逆迭代器）

sqli-labs第一关--报错注入练习

python之判断字符里面有没有|8

浅谈MFC CSting类拼接效率

关于多项式的一点研究及其在ACM竞赛中的应用关于多项式的一点研究及其在ACM竞赛中的应用

C和java中关于字符串与字符数组的定义和转化

Java：String类字符串与数组之间的转换

Java中 byte[] 数组与 String 字符串的转化

回文树学习小结

codeforces 838D D. Airplane Arrangements 构造法推公式

HDU Reorder the Books

POJ 1284 Primitive Roots (欧拉函数&原根定理)

查找文件中的字符串

hdu 4741 Save Labman No.004（计算几何） Save Labman No.004