题目地址：POJ，HDU
POJ WA, HDU AC不知道为什么.....
在某一个危险节点查好后，直接标记为非危险节点，下次就不用查了，省时间
某一个串正的反着算一个，所以给同一个串标号，开个数组保存是否查到该串
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#include<algorithm>
using namespace std;
const int letter=26;
char virus[1000+5];
char program[5100000+5];
struct Node{Node* pChilds[letter];Node* pPrev;bool bBadNode; int idx;void init(){memset(pChilds,0,sizeof(pChilds));pPrev=NULL; idx=0; bBadNode=false;}
}tree[500000+10];
int nNode;
bool done[250+5]; //保存该节点是否计数过
void Insert(Node* root,char* s,int k)
{for(int i=0;s[i];i++){if(root->pChilds[s[i]-'A']==NULL)root->pChilds[s[i]-'A']=tree+nNode++;root=root->pChilds[s[i]-'A'];}root->bBadNode=true;root->idx=k;
}
void BuildDfa()
{for(int i=0;i<letter;i++)tree[0].pChilds[i]=tree+1;tree[1].pPrev=tree;tree[0].pPrev=NULL;queue<Node*> Q;Q.push(tree+1);while(!Q.empty()){Node* root=Q.front(); Q.pop();for(int i=0;i<letter;i++){Node* p=root->pChilds[i];if(p==NULL) continue;Node* pPrev=root->pPrev;while(pPrev!=NULL){if(pPrev->pChilds[i]!=NULL){p->pPrev=pPrev->pChilds[i];if(p->pPrev->bBadNode) p->bBadNode=true;break;}else pPrev=pPrev->pPrev;}Q.push(p);}}
}
int SearchDfa()
{Node* p=tree+1;int cnt=0;for(int i=0;program[i];i++){for(;;){if(p->pChilds[program[i]-'A']!=NULL){p=p->pChilds[program[i]-'A'];Node* pPrev=p;while(pPrev->bBadNode){if(pPrev->idx){if(!done[pPrev->idx]) {cnt++; done[pPrev->idx]=true;}}pPrev->bBadNode=false;pPrev=pPrev->pPrev;}break;} else p=p->pPrev;} } return cnt;
}
void Read(char *s)
{int p=0,n;char ch,w;ch=getchar();while(ch=='\n') ch=getchar();do{if(ch==' ') continue;if(ch=='['){scanf("%d",&n);scanf("%c",&w);getchar();for(int i=0;i<n;i++) s[p++]=w;}else s[p++]=ch;ch=getchar();}while(ch!='\n');s[p++]='\0';
}
int main()
{int T,n; cin>>T;while(T--){cin>>n;nNode=2;memset(tree,0,sizeof(tree)); memset(done,false,sizeof(done));for(int i=1;i<=n;i++){scanf("%s",virus);Insert(tree+1,virus,i);reverse(virus,virus+strlen(virus));Insert(tree+1,virus,i);}BuildDfa();Read(program); cout<<SearchDfa()<<endl;}return 0;
}