[hdu3695]Computer Virus on Planet Pandora(AC自动机)

题意：正反匹配模式串。
解题关键：需要建立vis数组，不然会超时，因为匹配串会匹配很多次模式串，而我们只记录一次，从而第二次以后可以直接break。
复杂度可从$O(500W)$降到$O(25W)$
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int N=26;
  5 const int MAXN=250010;
  6 bool vis[MAXN];
  7 int ans;
  8 struct Trie{//数组形式 
  9     int Next[MAXN][N],Fail[MAXN],End[MAXN],root,tot;//大小为所以匹配字符串的总和 
 10     int newnode(){//结构体内部用 
 11         for(int i=0;i<N;i++) Next[tot][i]=-1;
 12         End[tot++]=0;
 13         return tot-1;
 14     }
 15     void init(){
 16         tot=0;
 17         root=newnode();
 18     }
 19     void insert(char buf[]){
 20         int len=strlen(buf);
 21         int now=root;//now是temp指针 
 22         for(int i=0;i<len;i++){
 23             int k=buf[i]-'A';
 24             if(Next[now][k]==-1)  Next[now][k]=newnode();//next数组代表的是下一个字符索引 
 25             now=Next[now][k];
 26         }
 27         End[now]++;//end数组是当前字符串的个数.字典中可能有相同的单词，若只算一次，改为1. 
 28     }
 29     void build(){//构造fail指针，后缀是某些前缀 
 30         queue<int>que;
 31         Fail[root]=root;
 32         for(int i=0;i<N;i++){ 
 33             if(Next[root][i]==-1) Next[root][i]=root;
 34             else{
 35                 Fail[Next[root][i]]=root;
 36                 que.push(Next[root][i]);
 37             }
 38         } 
 39         while(!que.empty()){//bfs,会将所有的匹配子串都遍历到 
 40             int now=que.front();
 41             que.pop();
 42             for(int i=0;i<N;i++){
 43                 if(Next[now][i]==-1) Next[now][i]=Next[Fail[now]][i];
 44                 else{
 45                     Fail[Next[now][i]]=Next[Fail[now]][i];//fail指向最长的 
 46                     que.push(Next[now][i]);
 47                 }
 48             }
 49         }
 50     }
 51     void query(char buf[]){
 52         int len=strlen(buf),now=root,res=0;
 53         for(int i=0;i<len;i++){
 54             now=Next[now][buf[i]-'A'];
 55             int temp=now;
 56             while(temp!=root){
 57                 if(vis[temp]) break;
 58                  ans+=End[temp];
 59                  End[temp]=0;
 60                  vis[temp]=true;
 61                 temp=Fail[temp];
 62             }
 63         }
 64     }
 65 };
 66 
 67 Trie ac;
 68 char buf[5100010];
 69 int n,m;
 70 int input(){
 71     getchar();
 72     char ch;
 73     int slen=0;
 74     while((ch=getchar())!='
'){
 75         if(ch!='[') buf[slen++]=ch;
 76         else{
 77             int x;
 78             scanf("%d%c",&x,&ch);
 79             while(x--) buf[slen++]=ch;
 80             getchar();
 81         }
 82     }
 83     buf[slen]='';
 84     return slen;
 85 }
 86 
 87 
 88 int main(){
 89        int t;
 90        scanf("%d",&t);
 91        while(t--){
 92            memset(vis,0,sizeof vis);
 93            ans=0;
 94            ac.init();
 95            scanf("%d",&n);
 96            for(int i=0;i<n;i++){
 97                scanf("%s",buf);
 98                ac.insert(buf);
 99         }
100         ac.build();
101         int len=input();
102         ac.query(buf);
103         reverse(buf,buf+len);
104         ac.query(buf);
105         printf("%d
",ans);
106     }
107     return 0;
108 }