1 #include <cstdio>  2 #include <cstring>  3 #include <map>  4 #define max(x, y) ((x)>(y) ? (x):(y))  5 const int digit=100000000;  6 const int sizeOfLen=64;  7 const int sizeOfMemory=1024;  8 const int sizeOfType=64;  9  10 struct bigint 11 { 12     int len; 13     int a[20]; 14     inline bigint():len(1) {memset(a, 0, sizeof(a));} 15     inline bigint & operator = (int x) {a[0]=x; return *this;} 16     inline bigint & operator += (bigint x) 17     { 18         len=max(len, x.len); 19         for (int i=0;i<len;i++) 20         { 21             a[i]+=x.a[i]; 22             a[i+1]+=a[i]/digit; 23             a[i]%=digit; 24         } 25         for ( ;a[len];len++) a[len+1]=a[len]/digit, a[len]%=digit; 26         return *this; 27     } 28     inline void print() 29     { 30         printf("%d", a[len-1]); 31         for (int i=len-2;i>=0;i--) printf("%08d", a[i]); 32         putchar(‘\n‘); 33     } 34 }; 35  36 int N, M, P; 37 char str[sizeOfLen]; 38 bigint f[sizeOfLen][sizeOfMemory]; 39 std::map<char, int> ord; 40 inline void dynamicProgram(); 41  42 namespace trieDfa 43 { 44     struct node 45     { 46         int order; 47         bool end; 48         node * fail; 49         node * ch[sizeOfType]; 50     }; 51     node memory[sizeOfMemory]; int port; 52     node * dfa=memory; 53     inline node * newnode() 54     { 55         node * ret=memory+port; 56         ret->order=port++; 57         ret->end=0; 58         ret->fail=NULL; 59         memset(ret->ch, 0, sizeof(ret->ch)); 60         return ret; 61     } 62     inline void clear() {port=0; dfa=newnode();} 63  64     inline void insert(char * s) 65     { 66         int len=strlen(s); 67         node * t=dfa; 68         for (int i=0;i<len;i++) 69         { 70             if (!t->ch[ord[str[i]]]) t->ch[ord[str[i]]]=newnode(); 71             t=t->ch[ord[str[i]]]; 72         } 73         t->end=1; 74     } 75     inline void buildDfa() 76     { 77         static node * queue[sizeOfMemory]; 78         int l=0, r=0; 79  80         dfa->fail=dfa; 81         for (int i=0;i<N;i++) 82             if (!dfa->ch[i]) dfa->ch[i]=dfa; 83             else dfa->ch[i]->fail=dfa, queue[r++]=dfa->ch[i]; 84  85         for ( ;l<r; ) 86         { 87             node * u=queue[l++]; 88             u->end|=u->fail->end; 89             for (int i=0;i<N;i++) 90                 if (u->ch[i]) 91                 { 92                     u->ch[i]->fail=u->fail->ch[i]; 93                     queue[r++]=u->ch[i]; 94                 } 95                 else 96                     u->ch[i]=u->fail->ch[i]; 97         } 98     } 99 }100 101 int main()102 {103     scanf("%d %d %d", &N, &M, &P);104     scanf("%s", str);105     for (int i=0;i<N;i++) ord[str[i]]=i;106     trieDfa::clear();107     for (int i=0;i<P;i++)108     {109         scanf("%s", str);110         trieDfa::insert(str);111     }112 113     dynamicProgram();114 115     return 0;116 }117 inline void dynamicProgram()118 {119     bigint ret;120 121     trieDfa::buildDfa();122 123     f[0][0]=1;124     for (int i=0;i<M;i++)125         for (int j=0;j<trieDfa::port;j++)126             for (int k=0;k<N;k++) if (!trieDfa::dfa[j].ch[k]->end)127                 f[i+1][trieDfa::dfa[j].ch[k]->order]+=f[i][j];128     ret=0;129     for (int i=0;i<trieDfa::port;i++) if (!trieDfa::dfa[i].end)130         ret+=f[M][i];131     ret.print();132 }

  1 #include <cstdio>  2 #include <cstring>  3 const int sizeOfVirus=512;  4 const int sizeOfText=10025;  5 const int sizeOfType=128;  6 const int sizeOfMemory=100025;  7   8 int N, M;  9 char str[sizeOfText]; 10 int virus[sizeOfMemory]; 11 bool vis[sizeOfVirus]; 12  13 namespace IOspace 14 { 15     inline int getint() 16     { 17         register int num=0; 18         register char ch; 19         do ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 20         do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 21         return num; 22     } 23     inline void putint(int num) 24     { 25         char stack[10]; 26         register int top=0; 27         for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 28         for ( ;top;top--) putchar(stack[top]); 29     } 30 } 31  32 namespace trieDfa 33 { 34     struct node 35     { 36         int order; 37         bool end; 38         node * fail, * last; 39         node * ch[sizeOfType]; 40     }; 41     node memory[sizeOfMemory]; int port; 42     node * dfa=memory; 43     inline node * newnode() 44     { 45         node * ret=memory+port; 46         ret->order=port++; 47         ret->end=false; 48         ret->fail=ret->last=NULL; 49         memset(ret->ch, 0, sizeof(ret->ch)); 50         return ret; 51     } 52     inline void clear() {port=0; dfa=newnode();} 53  54     inline void insert(char * s, int k) 55     { 56         int len=strlen(s); 57         node * t=dfa; 58         for (int i=0;i<len;i++) 59         { 60             if (!t->ch[s[i]]) t->ch[s[i]]=newnode(); 61             t=t->ch[s[i]]; 62         } 63         t->end=true; 64         virus[t->order]=k; 65     } 66     inline void buildDfa() 67     { 68         static node * queue[sizeOfMemory]; 69         int l=0, r=0; 70  71         dfa->fail=dfa; 72         for (int i=0;i<sizeOfType;i++) 73             if (!dfa->ch[i]) dfa->ch[i]=dfa; 74             else dfa->ch[i]->fail=dfa, queue[r++]=dfa->ch[i]; 75  76         for ( ;l<r; ) 77         { 78             node * u=queue[l++]; 79             for (int i=0;i<sizeOfType;i++) 80                 if (u->ch[i]) 81                 { 82                     u->ch[i]->fail=u->fail->ch[i]; 83                     u->ch[i]->last=u->ch[i]->fail->end?u->ch[i]->fail:u->ch[i]->fail->last; 84                     queue[r++]=u->ch[i]; 85                 } 86                 else 87                     u->ch[i]=u->fail->ch[i]; 88         } 89     } 90     inline bool search(char * s) 91     { 92         bool flag=0; 93         int len=strlen(s); 94  95         node * t=dfa; 96         memset(vis, 0, sizeof(vis)); 97         for (int i=0;i<len;i++) 98         { 99             t=t->ch[s[i]];100             if (t->end) vis[virus[t->order]]=flag=true;101             for (node * j=t->last;j;j=j->last)102                 vis[virus[j->order]]=flag=true;103         }104 105         return flag;106     }107 }108 109 int main()110 {111     int tot=0;112 113     N=IOspace::getint();114     trieDfa::clear();115     for (int i=1;i<=N;i++)116     {117         scanf("%s", str);118         trieDfa::insert(str, i);119     }120     trieDfa::buildDfa();121 122     M=IOspace::getint();123     for (int i=1;i<=M;i++)124     {125         scanf("%s", str);126         bool flag=trieDfa::search(str);127         tot+=flag;128 129         if (flag)130         {131             printf("web %d:", i);132             for (int i=1;i<=N;i++) if (vis[i])133                 putchar(‘ ‘), IOspace::putint(i);134             putchar(‘\n‘);135         }136     }137     printf("total: %d\n", tot);138 139     return 0;140 }