3 aaa bbb ccc 2 aaabbbccc bbaacc
web 1: 1 2 3 total: 1
#include<cstdio> #include<set> using namespace std; const int kind = 128; //有多少种字符 const int N = 505; const int M = 10005; struct node { node *next[kind]; node *fail; int id;//病毒编号 int cnt; //是不是病毒单词的结尾 node() { for(int i = 0; i < kind; i++) next[i] = NULL; cnt = 0; //0表示不是单词结尾 fail = NULL; } }*q[200*N]; node *root; int head, tail; char web[M]; char vir[205]; set<int> id_set; //记录每个网站的病毒编号,因为一个病毒可能会在一个网站出现多次,set可以直接去重 set<int> ::iterator it; void Insert(char *str, int id) { node *p = root; int i = 0, index; while(str[i]) { index = str[i] - ' '; if(p->next[index] == NULL) p->next[index] = new node(); p = p->next[index]; i++; } p->cnt++; p->id = id; } void build_ac_automation(node *root) { root->fail = NULL; q[tail++] = root; node *p = NULL; while(head < tail) { node *temp = q[head++]; for(int i = 0; i < kind; 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 Query(char *str) { id_set.clear(); int i = 0, index; node *p = root; while(str[i]) { index = str[i] - ' '; while(p->next[index] == NULL && p != root) p = p->fail; p = p->next[index]; if(p == NULL) p = root; node *temp = p; while(temp != root && temp->cnt > 0) { id_set.insert(temp->id); temp = temp->fail; } i++; } return id_set.size(); } int main() { int m, n; while(~scanf("%d",&n)) { int total = 0; head = tail = 0; root = new node(); for(int i = 1; i <= n; i++) { scanf("%s", vir); Insert(vir, i); } build_ac_automation(root); scanf("%d",&m); for(int i = 1; i <= m; i++){ scanf("%s",web); int s = Query(web); if(s) { total++; printf("web %d:", i); for(it = id_set.begin(); it != id_set.end(); it++) printf(" %d", *it); printf("\n"); } } printf("total: %d\n", total); } return 0; }
hdu 2896 病毒侵袭(AC自动机),布布扣,bubuko.com
原文:http://blog.csdn.net/lyhvoyage/article/details/38586077