HDU 2896 病毒侵袭（AC自动机）

AC自动机水题

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#include <set>
using namespace std;

struct node{
int tag;
node *fail;
node *son[128];
};

node word[500*200+5];
node *root;
set<int>ans;//set来存储病毒编号
int e = 0;

node *newnode(){
word[e].tag = 0;
word[e].fail = NULL;
for (int i = 0; i < 128; i++)word[e].son[i] = NULL;
return &word[e++];
}

void add(string word, int tag){
node *now = root;
int len = word.size();
for (int i = 0; i < len; i++){
int id = word[i];
if (now->son[id] == NULL)
now->son[id] = newnode();
if (i == len - 1)now->son[id]->tag = tag;
now = now->son[id];
}
}

void AC_automation(){
queue<node *>q;
node *now = root;
now->fail = NULL;
q.push(now);

while (!q.empty()){
now = q.front();
q.pop();
for (int i = 0; i < 128; i++){
if (now == root){
if (now->son[i] != NULL){
now->son[i]->fail = root;
q.push(now->son[i]);
}
}
else{
if (now->son[i] != NULL){
node *temp = now->fail;
while (temp != NULL){
if (temp->son[i] != NULL){
now->son[i]->fail = temp->son[i];
break;
}
temp = temp->fail;
}
if (temp == NULL)now->son[i]->fail = root;
q.push(now->son[i]);
}
}
}
}
}

void solve(string s){
node *now = root;
int len = s.size();
for (int i = 0; i < len; i++){
int id = s[i];
while (now->son[id] == NULL&&now != root)now = now->fail;
now = (now->son[id] == NULL) ? root : now->son[id];
node *temp = now;
while (temp != root){
if (temp->tag != 0){
ans.insert(temp->tag);
//注意这里不能把tag修改为0，防止干扰之后的查找
//temp->tag = 0;
}
temp = temp->fail;
}

}
}

int main()
{
int n, m;
string s;
cin >> n;
e = 0;
root = newnode();
for (int i = 0; i < n; i++){
cin >> s;
add(s, i + 1);
}
AC_automation();
cin >> m;
int cnt = 0;//记录web的个数
for (int i = 1; i <= m; i++){
cin >> s;
ans.clear();
solve(s);
if (ans.size() != 0){
cnt++;
cout << "web " << i << ":";
for (set<int>::iterator it = ans.begin(); it != ans.end(); it++)
cout << " " << *it;
cout << endl;
}
}
cout << "total: " << cnt << endl;
}