HDU 4787 GRE Words Revenge 在线AC自动机

本文主要是介绍HDU 4787 GRE Words Revenge 在线AC自动机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4787

构造两个自动机当一个自动机大于节点上限，就将BUFF全部加入AC
有个问题就是TOP在1000的时候能AC 5000和500就会WA不是很懂为什么

代码：

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 100000 + 10;
struct AcTrie{int ch[maxn][2],tot,v[maxn],fail[maxn];void Init(){memset( ch[0] , 0 ,sizeof ch[0]);v[0] = 0;tot = 1;}int NewNode(){memset( ch[tot] , 0, sizeof ch[0] );v[tot] = 0;return tot++;}void Insert(char * s){int cur = 0;while(*s){int idx = *s - '0';if(!ch[cur][idx]){ch[cur][idx] = NewNode();}cur = ch[cur][idx];s++;}v[cur] = 1;}void GetFail(){queue<int> Q;Q.push(0);fail[0] = -1;while(!Q.empty()){int cur = Q.front();Q.pop();for(int idx = 0;idx < 2;++idx){if(ch[cur][idx]){int f = fail[cur];while(~f && !ch[f][idx]) f = fail[f];fail[ch[cur][idx]] = (f == -1) ? 0 : ch[f][idx];Q.push(ch[cur][idx]);}}}}int Search(char *s){int cur = 0,ret = 0,f;while(*s){int idx = *s - '0';if(!ch[cur][idx]){f = fail[cur];while(f != -1 && !ch[f][idx]) f = fail[f];cur = (f == -1) ? 0 : ch[f][idx];}else cur = ch[cur][idx];f = cur;while(f){ret += v[f];f = fail[f];}s++;}return ret;}
}ac,buff;
const int maxnn = 5000000 + 50,TOP = 999;
char str[maxnn],tmp[maxnn];void DFS(int rt1,int rt2){ac.v[rt1] = ac.v[rt1] | buff.v[rt2];for(int i = 0;i < 2;++i){if(ac.ch[rt1][i] && buff.ch[rt2][i]) DFS(ac.ch[rt1][i],buff.ch[rt2][i]);else if(!ac.ch[rt1][i] && buff.ch[rt2][i]) DFS(ac.ch[rt1][i] = ac.NewNode(),buff.ch[rt2][i]);}
}
void getRev(int k){int len = strlen(str + 1);char* tmp_s = str + 1,*tmp_tmp = tmp + 1;tmp_tmp[len] = 0;for(int i = 0;i < len;++i) tmp_tmp[i] = tmp_s[ (i + k) % len ];
}
int main(){int T,ca = 0;sf("%d",&T);tmp[0] = '#';while( T-- ){int n,pre = 0;sf("%d",&n);ac.Init();buff.Init();ac.GetFail();buff.GetFail();pf("Case #%d:\n",++ca);for(int i = 0;i < n;++i){sf("%s",str);getRev(pre);if(str[0] == '+') buff.Insert(tmp + 1);else{if(buff.tot > TOP){DFS(0,0);ac.GetFail();buff.Init();buff.GetFail();}else buff.GetFail();pf("%d\n",pre = (buff.Search(tmp + 1) + ac.Search(tmp + 1)));}}}
}