本文共 2666 字，大约阅读时间需要 8 分钟。
题意：中文......
思路：
这里就知识循环枚举每一个网址即可，set记录每个网址包含的病毒的编号。
//#pragma comment(linker,"/STACK:327680000,327680000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 57#define N 1000007using namespace std;struct node{ int cnt; node *fail; node *next[95]; void newnode() { cnt = 0; fail = NULL; for (int i = 0; i < 95; ++i) { next[i] = NULL; } }};set iSet[1007];struct AC_Automat{public: node *q[N],*root,H[N]; int fr,tl; int t; void init() { fr = tl = 0; t = 0; H[t].newnode(); root = &H[t++]; for (int i = 0; i <= 1000; ++i) iSet[i].clear(); } void insert(char *s,int no) { int i,k; int len = strlen(s); node *p = root; for (i = 0; i < len; ++i) { k = s[i] - 32; if (p->next[k] == NULL) { H[t].newnode(); p->next[k] = &H[t++]; } p = p->next[k]; } p->cnt = no; } void build() { int i; root->fail = NULL; q[tl] = root; node *p; while (fr <= tl) { node *tmp = q[fr++]; for (i = 0; i < 95; ++i) { if (tmp->next[i]) { if (tmp == root) tmp->next[i]->fail = root; else { p = tmp->fail; while (p != NULL) { if (p->next[i]) { tmp->next[i]->fail = p->next[i]; break; } p = p->fail; } if (p == NULL) tmp->next[i]->fail = root; } q[++tl] = tmp->next[i]; } } } } void query(char *s,int no) { int i,k; int len = strlen(s); node *p = root; for (i = 0; i < len; ++i) { k = s[i] - 32; while (p->next[k] == NULL && p != root) p = p->fail; p = p->next[k]; if (p == NULL) p = root; node *tmp = p; while (tmp != root) { if (tmp->cnt != 0) { iSet[no].insert(tmp->cnt); } tmp = tmp->fail; } } }}ac;int n,m;char s1[202],s2[10007];int main(){ int i; while (~scanf("%d",&n)) { ac.init(); for (i = 1; i <= n; ++i) { scanf("%s",s1); ac.insert(s1,i); } ac.build(); scanf("%d",&m); for (i = 1; i <= m; ++i) { scanf("%s",s2); ac.query(s2,i); } int tol = 0; set ::iterator it; for (i = 1; i <= m; ++i) { if (iSet[i].size() >= 1) { printf("web %d:",i); tol++; for (it = iSet[i].begin(); it != iSet[i].end(); ++it) { printf(" %d",*it); } printf("\n"); } } printf("total: %d\n",tol); } return 0;}
转载地址：http://qilko.baihongyu.com/