hdu 3065 病毒侵袭持续中 (ac自动机)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月18日 星期四 00时17分38秒
  4File Name :code/hdu/3065.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <stack>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <deque>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27using namespace std;
 28const double eps = 1E-8;
 29const int dx4[4]={1,0,0,-1};
 30const int dy4[4]={0,-1,1,0};
 31const int inf = 0x3f3f3f3f;
 32const int sizTrie = 26;
 33map<int,int>mp;
 34char ill[1005][50];
 35struct Trie
 36{
 37    struct Node
 38    {
 39	Node *nxt[sizTrie];
 40	Node *fail;
 41	int cnt;
 42	int id;
 43	Node()
 44	{
 45	    for ( int i = 0 ; i < sizTrie; i++) nxt[i]=NULL;
 46	    cnt = 0 ;
 47	    id = 0 ;
 48	    fail = NULL;
 49	}
 50    };
 51    Node *root;
 52    void init()
 53    {
 54	root = new Node();
 55    }
 56    void Insert(char *s,int x)
 57    {
 58	int len = strlen(s);
 59	Node *u = root;
 60	for ( int i = 0 ; i < len ; i++ )
 61	{
 62	    int v = s[i]-'A';
 63	    if (u->nxt[v]==NULL) u->nxt[v] = new Node();
 64	    u = u->nxt[v];
 65	}
 66	u->cnt++;
 67	u->id = x;
 68//	cout<<"s:"<<s<<" cnt:"<< u->cnt <<endl;
 69    }
 70    void getFail()
 71    {
 72	root->fail = root;
 73	queue<Node*>Q;
 74	for ( int i = 0 ; i < sizTrie ; i++)
 75	{
 76	    if (root->nxt[i]==NULL)
 77		root->nxt[i] = root;
 78	    else
 79	    {
 80		root->nxt[i]->fail = root;
 81		Q.push(root->nxt[i]);
 82	    }
 83	}
 84	while (!Q.empty())
 85	{
 86	    Node * cur = Q.front();
 87	    Q.pop();
 88	    for ( int i = 0 ; i < sizTrie ; i++)
 89	    {
 90		if (cur->nxt[i]==NULL)
 91		    cur->nxt[i] = cur->fail->nxt[i];
 92		else
 93		{
 94		    cur->nxt[i]->fail = cur->fail->nxt[i];
 95		    Q.push(cur->nxt[i]);
 96		}
 97	    }
 98	}
 99    }
100	void Search(char *s)
101	{
102	    int len = strlen(s);
103	    Node *u = root;
104	    mp.clear();
105	    for ( int i = 0 ; i < len ; i++)
106	    {
107		if (s[i]<'A'||s[i]>'Z')
108		{
109		    u = root; //不要忘记，出现不可能被匹配的字符，相当于重新初始化了
110		    continue;
111		}
112		int v = s[i]-'A';
113		u = u->nxt[v];
114		Node * tmp = u;
115		while (tmp!=root)
116		{
117		    if (tmp->id)
118		    mp[tmp->id]++;
119		    tmp = tmp->fail;
120		}
121	    }
122	    for (auto it = mp.begin() ; it!=mp.end() ; it++)
123//		if (strcmp(ill[it->fst],"")!=0)
124		printf("%s: %d\n",ill[it->fst],it->sec);
125/*	    //sort(ans.begin(),ans.end());
126	    int siz = ans.size();
127	    cout<<"anszie:"<<ans.size()<<endl;
128	    for ( int i = 0 ; i < siz;  i++)
129	    {
130		printf("%s: %d\n",ill[ans[i].fst],ans[i].sec);
131	    }   */
132	}
133}ac;
134const int N=2E6+7;
135int n;
136char str[N];
137int main()
138{
139	#ifndef  ONLINE_JUDGE 
140	freopen("code/in.txt","r",stdin);
141  #endif
142	while (scanf("%d",&n)!=EOF)
143	{   
144	    ac.init();
145	    for ( int i = 1 ; i <= n ; i++)
146	    {
147		scanf("%s",ill[i]);
148		ac.Insert(ill[i],i);
149	    }
150	    ac.getFail();
151	    scanf("%s",str);
152	    //	cout<<"str:"<<str<<endl;
153	    ac.Search(str);
154	}
155  #ifndef ONLINE_JUDGE  
156  fclose(stdin);
157  #endif
158    return 0;
159}