首页 > 代码库 > AC自动机 - 多模式串的匹配运用 --- HDU 2896

AC自动机 - 多模式串的匹配运用 --- HDU 2896

病毒侵袭

Problem‘s Link:http://acm.hdu.edu.cn/showproblem.php?pid=2896


 

Mean: 

 中文题,不解释。

analyse:

AC自动机的运用,多模式串匹配。就是有几个细节要注意,在这些细节上卡了半天了。

1)输出的网站编号和最终的病毒网站数不是一样的;

2)next指针要设128,不然会爆栈;

3)同理,char转换为int时,base要设为31;

Time complexity:o(n)+o(ml) 

 

Source code:

 

// Memory   Time// 1347K     0MS// by : Snarl_jsb// 2014-09-30-11.01#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define LL long longusing namespace std;const int N = 10010;char str[N];struct node{    node *next[128];     //  每个结点都对应128个字母的指针    node *fail;     //      失配指针    int count;      //    int num;    node()      //  构造函数初始化    {        for(int i = 0; i < 128; i++)            next[i] = NULL;        count = 0;        fail = NULL;        num=0;    }}*q[50*N];node *root;int head, tail;void Insert(char *str,int num) //   插入单词.相当于构建一个Trie树{    node *p = root;    int i = 0, index;    while(str[i]) {        index = str[i] - 31; //  转化为相对数字来存        if(p->next[index] == NULL) // 该字母未插入过            p->next[index] = new node();    //  为该字母申请一个结点        p = p->next[index];     //   移至下一个        i++;    }    p->count++;     //      记录该结点的单词总共插入的次数    p->num=num;}void build_ac_automation(node *root)        //      bfs建立fail指针{    root->fail = NULL;    q[tail++] = root;    while(head < tail) {        node *temp = q[head++];        node *p = NULL;        for(int i = 0; i < 128; i++) {            if(temp->next[i] != NULL) {                if(temp == root) temp->next[i]->fail = root;                else {                    p = temp->fail;                    while(p != NULL) {                        if(p->next[i] != NULL) {                            temp->next[i]->fail = p->next[i];                            break;                        }                        p = p->fail;                    }                    if(p == NULL) temp->next[i]->fail = root;                }                q[tail++] = temp->next[i];            }        }    }}int total=0;int Query(node *root,int num)       //  匹配 + 统计{    int i = 0, cnt = 0, index;    node *p = root;    int idx=0;    int ans[100];    while(str[i])    {        index = str[i] - 31;        while(p->next[index] == NULL && p != root) //前缀是相同的,所以不管哪个指针走到了count不为0的结点上,那么该结点所代表的单词就匹配成功            p = p->fail;//失配情况下,p指针指向p->fail.(相当于KMP的next数组)        p = p->next[index];//由于现在所在的位置是父节点,所以需要向下移动一个位置        if(p == NULL)            p = root; //如果匹配失败,移动到root,重新开始匹配        node *temp = p;//        while(temp != root && temp->count != -1)  //统计--如果匹配成功,那么count>1,表示该结点代表的单词数量;否则表示该结点没有单词        {            if(temp->count>0)            {                cnt ++; //统计该单词出现的次数                ans[++idx]=temp->num;            }//            temp->count = -1;   //标记为-1,表示该单词已经加入了cnt中,下次就不用重复统计            temp = temp->fail;//判断整条链上的匹配情况        }        i++;    }    if(idx==0)        return 0;    printf("web %d: ",num);    sort(ans+1,ans+1+idx);    total++;    for(int i=1;i<idx;++i)    {        printf("%d ",ans[i]);    }    printf("%d\n",ans[idx]);    return cnt;}int main(){    int n;    cin>>n;    head=tail=0;    root=new node();    for(int i=1;i<=n;++i)    {        scanf("%s",str);        Insert(str, i);    }    build_ac_automation(root);      //  建树    int m;    cin>>m;    total=0;    for(int i=1;i<=m;++i)    {        scanf("%s",str);        Query(root,i);    }    printf("total: %d\n",total);    return 0;}

  

AC自动机 - 多模式串的匹配运用 --- HDU 2896