POJ/3987.cc

   1 #include <cstdio>
   2 #include <cstring>
   3 #include <queue>
   4 #include <algorithm>
   5
   6 struct node
   7 {
   8         int fail,flag,next[26];
   9 } ac[500000];
  10
  11 char s[5100001];
  12
  13 int count,len;
  14
  15 inline void insert(char *s)
  16 {
  17         int len=std::strlen(s),p=0;
  18         for (int i=0; i<len; ++i)
  19         {
  20                 int tmp=s[i]-'A';
  21                 if (!ac[p].next[tmp]) ac[p].next[tmp]=++count;
  22                 p=ac[p].next[tmp];
  23         }
  24         ac[p].flag=1;
  25 }
  26
  27 void build()
  28 {
  29         ac[0].fail=-1;
  30         std::queue<int> q;
  31         q.push(0);
  32         while (!q.empty())
  33         {
  34                 int u=q.front();
  35                 q.pop();
  36                 for (int i=0; i<26; i++)
  37                 {
  38                         int p=ac[u].next[i],tmp;
  39                         if (p)
  40                         {
  41                                 for (tmp=ac[u].fail; tmp!=-1; tmp=ac[tmp].fail)
  42                                         if (ac[tmp].next[i])
  43                                         {
  44                                                 ac[p].fail=ac[tmp].next[i];
  45                                                 break;
  46                                         }
  47                                 if (tmp==-1) ac[p].fail=0;
  48                                 q.push(p);
  49                         }
  50                 }
  51         }
  52 }
  53
  54 int solve()
  55 {
  56         int p=0,len=std::strlen(s),ans=0;
  57         for (int i=0; i<len; i++)
  58         {
  59                 int tmp=s[i]-'A';
  60                 while (p && !ac[p].next[tmp]) p=ac[p].fail;
  61                 p=ac[p].next[tmp];
  62                 int t=p;
  63                 while (t && ac[t].flag!=-1)
  64                 {
  65                         ans+=ac[t].flag;
  66                         ac[t].flag=-1;
  67                         t=ac[t].fail;
  68                 }
  69         }
  70         return ans;
  71 }
  72
  73 void init()
  74 {
  75         std::memset(ac,0,sizeof(ac));
  76         std::memset(s,0,sizeof(s));
  77         char st[1001];
  78         int n;
  79         count=0;
  80         scanf("%d",&n);
  81         for (int i=0; i<n; ++i)
  82         {
  83                 scanf("%s",st);
  84                 insert(st);
  85         }
  86         scanf("\n");
  87         char ch;
  88         len=0;
  89         for (scanf("%c",&ch); ch!='\n'; scanf("%c",&ch))
  90         {
  91                 if (ch=='[')
  92                 {
  93                         int tmp;
  94                         scanf("%d",&tmp);
  95                         scanf("%c",&ch);
  96                         while (tmp--) s[len++]=ch;
  97                         scanf("%c",&ch);
  98                 }
  99                 else s[len++]=ch;
 100         }
 101         s[len]='\0';
 102         build();
 103 }
 104
 105 int main()
 106 {
 107         int t;
 108         scanf("%d",&t);
 109         while (t--)
 110         {
 111                 init();
 112                 int ans=solve();
 113                 for (int i=0; i<len/2; ++i) std::swap(s[i],s[len-i-1]);
 114                 ans+=solve();
 115                 printf("%d\n",ans);
 116         }
 117 }