首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。