UVALive 5103 Computer Virus on Planet Pandora Description 求模式串出现的种数 AC自动机

题目链接：点击打开链接

题意：

case数

n个模式串

一个母串。

问：n个模式串出现的种数（一个模式串多次出现只算一次）

对于 "ABC" , 若母串出现了"CBA"这样的反串，也算出现了。

所以：

1

ABC

CBA

ans = 1

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxnode = 250*1000+10000; const int sigma_size = 26; struct Trie{ int ch[maxnode][sigma_size]; int val[maxnode]; //该单词在模式串中出现的次数 int last[maxnode]; int f[maxnode]; //失配数组 int num[maxnode]; //该单词出现在文本串的次数 int pre[maxnode]; //该单词的前驱 int len[maxnode]; //以该单词结尾的单词长度 int Char[maxnode]; //该单词对应的字母 int road[maxnode]; //路径压缩优化 针对计算模式串出现的种数 int sz; int Newnode() { val[sz] = f[sz] = last[sz] = len[sz] = num[sz] = 0; memset(ch[sz], 0, sizeof ch[sz]); return sz++; } void init(){ sz=0; Newnode(); } int idx(char c){ return c-'A'; } int insert(char *s){ int u = 0; for(int i = 0, c; s[i] ;i++){ c = idx(s[i]); if(!ch[u][c]) ch[u][c] = Newnode(); pre[ch[u][c]] = u; Char[ch[u][c]] = s[i]; len[ch[u][c]] = len[u]+1; road[ch[u][c]] = 1; u = ch[u][c]; } val[u] = 1; num[u] = 0; return u; } void getFail(){ queue
       
         q; for(int i = 0; i
        
         sz)lu[i]=1; int j = 0, i, c, temp; for(i = 0; T[i]; i++){ c = idx(T[i]); while(j && ch[j][c] == 0) j = f[j]; j = ch[j][c]; temp = j; while(temp && road[temp]){ if(val[temp]) { ++ans; val[temp] = 0; } road[temp] = 0; temp = f[temp]; } } } }ac; char s[1015], a[5100010], b[5100010], c; int n, num; int main() { int T; scanf("%d", &T); while (T-->0) { ac.init(); scanf("%d", &n); while(n--){ scanf("%s", s); ac.insert(s); } ac.getFail(); int top = 0; scanf("%s", a); int i = 0; while(a[i]){ if(a[i]!='[') b[top++] = a[i]; else { num = 0; i++; while( '0' <= a[i] && a[i] <= '9') num = num*10 + a[i]-'0', i++; c = a[i]; i++; while(num-- > 0){ b[top++] = c; } } i++; } a[top] = b[top] = 0; for(int i = top-1; i >= 0; i--)a[i] = b[top-i-1]; int ans = 0; ac.find_kind(b, ans); ac.find_kind(a, ans); printf("%d\n", ans); } return 0; }