题意：
给一个母串和多个模式串，求模式串在母串后翻转后的母串出现次数的的总和。
分析：
模板题
/*#include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <algorithm> 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 build(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<int> q; for(int i = 0; i<sigma_size; i++) if(ch[0][i]) q.push(ch[0][i]); int r, c, u, v; while(!q.empty()){ r = q.front(); q.pop(); for(c = 0; c<sigma_size; c++){ u = ch[r][c]; if(!u)continue; q.push(u); v = f[r]; while(v && ch[v][c] == 0) v = f[v]; //沿失配边走上去 如果失配后有节点 且 其子节点c存在则结束循环 f[u] = ch[v][c]; } } } void find(char *T){ //计算模式串出现的个数：（每种多次出现算多次） int j = 0; for(int i = 0, c, temp; T[i] ; i++){ c = idx(T[i]); while(j && ch[j][c]==0) j = f[j]; j = ch[j][c]; temp = j; while(temp){ num[temp]++; temp = f[temp]; } } } int find_kind(char *T){ //计算种数， 重复出现的不再计算(若多个询问则要在此处加for(i=0->sz)lu[i]=1; int j = 0, i, c, temp,ans=0; 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]; } } return ans; } }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.build(s); } ac.getFail(); int top = 0; scanf("%s", a); int i = 0,sum=0,id=0; while(a[i]!=‘\0‘){ if(a[i]==‘[‘){ i++; int len=0; while(a[i]>=‘0‘&&a[i]<=‘9‘){ len=len*10+a[i]-‘0‘; i++; } for(int j=0;j<len;++j) b[id++]=a[i]; i+=2; } else{ b[id++]=a[i]; i++; } } b[id]=0; //printf("%s\n",b); sum+=ac.find_kind(b); reverse(b,b+id); //printf("%s\n",b); sum+=ac.find_kind(b); printf("%d\n", sum); } return 0; }*/ #include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <complex> #include <cassert> #include <utility> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef pair<int,int> PII; typedef long long ll; #define lson l,m,rt<<1 #define pi acos(-1.0) #define rson m+1,r,rt<<11 #define All 1,N,1 #define read freopen("in.txt", "r", stdin) #define N 300010 const ll INFll = 0x3f3f3f3f3f3f3f3fLL; const int INF= 0x7ffffff; const int mod = 1000000007; char P[1010],T[6000000],T1[6000000]; int n; struct Trie{ int ch[N][26],val[N],f[N],num; void init(){ num=1; memset(ch,0,sizeof(ch)); memset(val,0,sizeof(val)); memset(f,0,sizeof(f)); } void build(char *s){ int u=0,len=strlen(s); for(int i=0;i<len;++i) { int v=s[i]-‘A‘; if(!ch[u][v]){ memset(ch[num],0,sizeof(ch[num])); ch[u][v]=num++; } u=ch[u][v]; } val[u]=1; //return u; } void getfail(){ queue<int>q; for(int i=0;i<26;++i) if(ch[0][i]) q.push(ch[0][i]); while(!q.empty()){ int r=q.front(); q.pop(); for(int i=0;i<26;++i) { int u=ch[r][i]; if(!u){ch[r][i] = ch[f[r]][i];continue;} q.push(u); int v=f[r]; while(v&&!ch[v][i])v=f[v]; f[u]=ch[v][i]; } } } int find(char *T){ int u=0,len=strlen(T),total=0; for(int i=0;i<len;++i){ int v=T[i]-‘A‘; while(u&&ch[u][v]==0) u=f[u]; u=ch[u][v]; int tmp=u; while(tmp){ if(val[tmp]){ total+=val[tmp]; val[tmp]=0; } tmp=f[tmp]; } } return total; } }ac; int main() { int t; scanf("%d",&t); while(t--){ ac.init(); scanf("%d",&n); while(n--){ scanf("%s",P); ac.build(P); } scanf("%s",T); // printf("%s",T); int id=0,tid=0,i=0; char tc; while(T[i]!=‘\0‘){ if(T[i]==‘[‘){ i++; int len=0; while(T[i]>=‘0‘&&T[i]<=‘9‘){ len=len*10+T[i]-‘0‘; i++; } for(int j=0;j<len;++j) T1[id++]=T[i]; i+=2; } else{ T1[id++]=T[i]; i++; } } T1[id]=0; // printf("%s\n",T1); int sum=0; sum+=ac.find(T1); reverse(T1,T1+id); //printf("%s\n",T1); sum+=ac.find(T1); printf("%d\n",sum); } return 0; }
HDU 3695-Computer Virus on Planet Pandora（ac自动机）
原文：http://www.cnblogs.com/zsf123/p/4780838.html