Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 327680/327680 K (Java/Others)
Total Submission(s): 2505 Accepted Submission(s): 614
可持久化,也就是可以在线,边询问边插入模式串,如果暴力每次插入后重建ac自动机,那么复杂度就是O(N*N),的,可以想到用分块(dalao是这么叫的);建立一个大的自动机,一个小的自动机,小的自动机规模是sqrt(N),大的是N,每次插入时在小的buf 里添加字串,重构自动机,当buf的规模超过sqrt(N)时,合并到大的自动机里大的重建,复杂度为O(sqrt(N) * N);合并就是buf 与ac 的字典树一起跑,如果ac里没有buf 的结点,就新建,然后权值|=buf.val[],(有节点也要| =,因为原来的不一定是单词,但现在是了);
1 //2017-07-15 19:28:18 2 //2017-07-15 20:10:10 3 #include<algorithm> 4 #include<iostream> 5 #include<cstdlib> 6 #include<cstdio> 7 #include<cmath> 8 #include<map> 9 #include"set" 10 #include"queue" 11 #include"vector" 12 #include"iomanip" 13 #include"cstring" 14 #define inf 1<<29 15 #define ll long long 16 #define re register 17 #define il inline 18 #define rep(i,a,b) for(register int i=a;i<=b;++i) 19 #define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 20 using namespace std; 21 const int N=100010; 22 char tmp[5000100],s[5000100]; 23 struct ACAutomation{ 24 int f[N],ch[N][2],lst[N],sz; 25 int val[N]; 26 il void init() { 27 sz=0;ch[0][0]=ch[0][1]=0;lst[0]=0; 28 //val[0]=0; 29 } 30 il int newnode(){ 31 ++sz; 32 ch[sz][0]=ch[sz][1]=f[sz]=lst[sz]=0; 33 val[sz]=0;// 34 return sz; 35 } 36 il bool search(char *s,int len) { 37 re int t=0,c; 38 for(re int i=0;i<len;++i){ 39 c=s[i]-‘0‘; 40 if(!ch[t][c]) 41 return 0; 42 t=ch[t][c]; 43 } 44 return val[t]; 45 } 46 il void insert(char *s,int len){ 47 re int t=0,c; 48 for(re int i=0;i<len;++i){ 49 c=s[i]-‘0‘; 50 if(!ch[t][c]) 51 ch[t][c]=newnode(); 52 t=ch[t][c]; 53 } 54 val[t]=1; 55 } 56 il void build() { 57 queue<int> q; 58 for(re int i=0;i<2;++i){ 59 if(ch[0][i]) 60 q.push(ch[0][i]),f[ch[0][i]]=0,lst[ch[0][i]]=0; 61 } 62 re int r,v,u; 63 while(!q.empty()) { 64 r=q.front();q.pop(); 65 for(re int c=0;c<2;++c) { 66 u=ch[r][c]; 67 if(!u) continue; 68 q.push(u); 69 v=f[r]; 70 while(v&&!ch[v][c]) v=f[v]; 71 f[u]=ch[v][c]; 72 lst[u] = val[f[u]] ? f[u] : lst[f[u]]; 73 } 74 } 75 } 76 il int run(char *s,int len) { 77 re int t=0,ans=0,c; 78 for(re int i=0;i<len;++i) { 79 c=s[i]-‘0‘; 80 while(t&&!ch[t][c]) t=f[t]; 81 t=ch[t][c]; 82 for(re int p=t;p;p=lst[p]) 83 ans+=val[p]; 84 } 85 return ans; 86 } 87 }; 88 ACAutomation ac,buf; 89 90 inline int gi() { 91 re int res=0,f=1;re char ch=getchar(); 92 while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘) ch=getchar(); 93 if(ch==‘-‘) f=-1,ch=getchar(); 94 while(ch>=‘0‘&&ch<=‘9‘) res=res*10+ch-‘0‘,ch=getchar(); 95 return res*f; 96 } 97 il void bfs() { 98 queue<int> U,V; 99 U.push(0),V.push(0); 100 re int u,v,r1,r2; 101 while(!U.empty()) { 102 u=U.front(),v=V.front(); 103 U.pop(),V.pop(); 104 for(re int c=0;c<2;++c) 105 if(buf.ch[u][c]) { 106 r1=buf.ch[u][c],r2=ac.ch[v][c]; 107 if(!r2) { 108 ac.ch[v][c]=ac.newnode(); 109 } 110 r2=ac.ch[v][c]; 111 ac.val[r2]|=buf.val[r1]; 112 U.push(r1),V.push(r2); 113 } 114 } 115 } 116 il void go() { 117 bfs(); 118 buf.init(); 119 ac.build(); 120 } 121 int main(){ 122 file("Y"); 123 re int cas=gi(); 124 rep(tt,1,cas) { 125 printf("Case #%d:\n",tt); 126 ac.init(); 127 buf.init(); 128 re int n=gi(); 129 re int l=0; 130 rep(qyp,1,n) { 131 scanf("%s",tmp); 132 re int len=strlen(tmp); 133 re int p=l%(len-1); 134 s[0]=tmp[0]; 135 for(re int i=1;i<=p;i++) s[i+len-1-p]=tmp[i]; 136 for(re int i=1;i<len-p;++i) s[i]=tmp[i+p]; 137 if(s[0]==‘+‘) { 138 if(buf.search(s+1,len-1)||ac.search(s+1,len-1)) continue; 139 buf.insert(s+1,len-1); 140 buf.build(); 141 if(buf.sz>333) go(); 142 } 143 else { 144 l=ac.run(s+1,len-1) + buf.run(s+1,len-1); 145 printf("%d\n",l); 146 } 147 } 148 } 149 return 0; 150 }
hdu 4787 GRE Words Revenge 在线AC自动机
原文：http://www.cnblogs.com/ypz999/p/7184907.html