$GRE\ Words\ Revenge$GRE Words Revenge

Time Limit: 20000/10000 MS (Java/Others)	Memory Limit: 327680/327680 K (Java/Others)
Total Submission(s): 3474	Accepted Submission(s): 843

Problem Description
　　Now Coach Pang is preparing for the Graduate Record Examinations as George did in 2011. At each day, Coach Pang can:
　　“+w”: learn a word w
　　“?p”: read a paragraph p, and count the number of learnt words. Formally speaking, count the number of substrings of p which is a learnt words.
　　Given the records of N days, help Coach Pang to find the count. For convenience, the characters occured in the words and paragraphs are only ‘0’ and ‘1’.

Input
　　The first line of the input file contains an integer T, which denotes the number of test cases. T test cases follow.
　　The first line of each test case contains an integer N (1 <= N <= 105), which is the number of days. Each of the following N lines contains either “+w” or “?p”. Both p and w are 01-string in this problem.
　　Note that the input file has been encrypted. For each string occured, let L be the result of last “?” operation. The string given to you has been shifted L times (the shifted version of string s1s2 … sk is sks1s2 … sk-1). You should decrypt the string to the original one before you process it. Note that L equals to 0 at the beginning of each test case.
　　The test data guarantees that for each test case, total length of the words does not exceed 105 and total length of the paragraphs does not exceed 5 * 106.

Output
　　For each test case, first output a line “Case #x:”, where x is the case number (starting from 1).
　　And for each “?” operation, output a line containing the result.

Sample Input
2
3
+01
+01
?01001
3
+01
?010
?011

Sample Output
Case #1:
2
Case #2:
1
0

Source
2013 Asia Chengdu Regional Contest

题目大意：

为了准备GRE考试，你打算花 n (n<=10⁵)(n<=10⁵ )天背单词。每天可以做两件事之一：
+w：学一个单词 w
?t：读一篇文章 t ，统计 t 有多少个连续子串是学过的单词。
为了简单起见，单词都是 01 串。学的单词长度总和不超过 10⁵ ，文章总长度不超过 5*10⁶
废话这么多，简单来说就是一个在线的AC自动机

TJ：

一开始只想到暴力算，每次询问都重新建立fail树，但是这样肯定会被特殊数据卡，然而大佬们就有一些神奇的思想（其实想法挺简单的，但就是想不到），对于这种瞎JB在线的问题，分块就完事儿了。但是自动机还能分块？
就是建立两个自动机，一个大的，一个小的，每次加入新单词就往小的里面加，如果小的里面的节点大于了sqrt(maxn)那就把小的往大的自动机里合并，这样每次更新小的自动机复杂度就是o(sqrt(maxn))，合并的时候只要把小的自动机里有的节点而大的自动机里没有的节点加到大的自动机里去就好了，复杂度O(sqrt(maxn))，对于每次查询操作，先对改变过的自动机重新建立fail树，分别在两个自动机里查然后加起来就好了。
注意还有简单的字符串处理

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 5e6+7;
const int max_size = 2;
bool built;
int T,n,len;
char in[maxn],text[maxn];
struct AC_automachine{
	struct Node{
		int cnt,next[max_size],fail,last;
	}node[maxn];
	int Size;
	queue<int> que;
	AC_automachine(){Size = 1;}
	void init(){
		for(int i=0;i<Size;i++){
			memset(node[i].next,0,sizeof(node[i].next));
			node[i].cnt = 0;
		}
		Size = 1;
	}
	void Insert(char *s){
		int now = 0;
		for(int i=0;i<len;i++){
			int inx = s[i]-'0';
			if(!node[now].next[inx]) node[now].next[inx] = Size++;
			now = node[now].next[inx];
		}
		node[now].cnt=1;
	}
	void build_fail(){
		node[0].fail = 0;
		que.push(0);
		while(!que.empty()){
			int u = que.front();
			que.pop();
			for(int i=0;i<max_size;i++){
				if(node[u].next[i]){
					if(u==0) node[node[u].next[i]].fail = node[node[u].next[i]].last = 0;
					else{
						int v = node[u].fail;
						while(v&&node[v].next[i]==0) v = node[v].fail;
						node[node[u].next[i]].fail = node[v].next[i];
						if(node[node[v].next[i]].cnt) node[node[u].next[i]].last = node[v].next[i];
						else node[node[u].next[i]].last = node[node[v].next[i]].last;
					}
					que.push(node[u].next[i]);
				}
			}
		}
	}
	int getres(int u){
		int res = 0;
		while(u){
			res+=node[u].cnt;
			u = node[u].last;
		}
		return res;
	}
	int match(char* s){
		int now = 0,res = 0;
		for(int i=0;i<len;i++){
			int inx = s[i]-'0';
			if(node[now].next[inx]) now = node[now].next[inx];
			else{
				while(now&&node[now].next[inx]==0) now = node[now].fail;
				now = node[now].next[inx];
			}
			res+=getres(now);
		}
		return res;
	}
	void unity(AC_automachine &x){
		queue<pair<int,int> > Q;
		Q.push(make_pair(0,0));
		while(!Q.empty()){
			pair<int,int> ft = Q.front();
			Q.pop();
			int now=ft.first,nowx=ft.second;
			for(int i=0;i<max_size;i++){
				if(x.node[nowx].next[i]){			//if have son
					if(!node[now].next[i]) node[now].next[i] = Size++;
					node[node[now].next[i]].cnt|=x.node[x.node[nowx].next[i]].cnt;
					Q.push(make_pair(node[now].next[i],x.node[nowx].next[i]));
				}
			}
		}
		x.init();
	}
}Aho_A,Aho_B;

int main(){
	scanf("%d",&T);
	for(int kase=1;kase<=T;kase++){
		Aho_A.init(); Aho_B.init();
		printf("Case #%d:\n",kase);
		scanf("%d",&n);
		int nn = sqrt(maxn),res = 0;
		built = false;
		for(int i=0;i<n;i++){
			scanf("%s",in);
			len = strlen(in)-1;
			int md = res%len;
			for(int j=0;j<len;j++) text[j] = in[(j+md)%len+1];
			text[len] = '\0';
			if(in[0]=='+'){
				Aho_B.Insert(text);
				built = false;
				if(Aho_B.Size>nn) Aho_A.unity(Aho_B);
			}
			else if(in[0]=='?'){
				if(!built){
					built = true;
					Aho_B.build_fail();
					Aho_A.build_fail();
				}
				res = Aho_A.match(text)+Aho_B.match(text);
				printf("%d\n",res);
			}
		}
	}
	return 0;
}

发现上边的code过了但是用了5959ms，然后发现更新标记出了点问题，每次都把大自动机重新求fail了，小改一下，1107ms pass

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 5e6+7;
const int max_size = 2;
bool built_A,built_B;
int T,n,len;
char in[maxn],text[maxn];
struct AC_automachine{
	struct Node{
		int cnt,next[max_size],fail,last;
	}node[maxn];
	int Size;
	queue<int> que;
	AC_automachine(){Size = 1;}
	void init(){
		for(int i=0;i<Size;i++){
			memset(node[i].next,0,sizeof(node[i].next));
			node[i].cnt = 0;
		}
		Size = 1;
	}
	void Insert(char *s){
		int now = 0;
		for(int i=0;i<len;i++){
			int inx = s[i]-'0';
			if(!node[now].next[inx]) node[now].next[inx] = Size++;
			now = node[now].next[inx];
		}
		node[now].cnt=1;
	}
	void build_fail(){
		node[0].fail = 0;
		que.push(0);
		while(!que.empty()){
			int u = que.front();
			que.pop();
			for(int i=0;i<max_size;i++){
				if(node[u].next[i]){
					if(u==0) node[node[u].next[i]].fail = node[node[u].next[i]].last = 0;
					else{
						int v = node[u].fail;
						while(v&&node[v].next[i]==0) v = node[v].fail;
						node[node[u].next[i]].fail = node[v].next[i];
						if(node[node[v].next[i]].cnt) node[node[u].next[i]].last = node[v].next[i];
						else node[node[u].next[i]].last = node[node[v].next[i]].last;
					}
					que.push(node[u].next[i]);
				}
			}
		}
	}
	int getres(int u){
		int res = 0;
		while(u){
			res+=node[u].cnt;
			u = node[u].last;
		}
		return res;
	}
	int match(char* s){
		int now = 0,res = 0;
		for(int i=0;i<len;i++){
			int inx = s[i]-'0';
			if(node[now].next[inx]) now = node[now].next[inx];
			else{
				while(now&&node[now].next[inx]==0) now = node[now].fail;
				now = node[now].next[inx];
			}
			res+=getres(now);
		}
		return res;
	}
	void unity(AC_automachine &x){
		queue<pair<int,int> > Q;
		Q.push(make_pair(0,0));
		while(!Q.empty()){
			pair<int,int> ft = Q.front();
			Q.pop();
			int now=ft.first,nowx=ft.second;
			for(int i=0;i<max_size;i++){
				if(x.node[nowx].next[i]){			//if have son
					if(!node[now].next[i]) node[now].next[i] = Size++;
					node[node[now].next[i]].cnt|=x.node[x.node[nowx].next[i]].cnt;
					Q.push(make_pair(node[now].next[i],x.node[nowx].next[i]));
				}
			}
		}
		x.init();
	}
}Aho_A,Aho_B;

int main(){
	scanf("%d",&T);
	for(int kase=1;kase<=T;kase++){
		Aho_A.init();Aho_B.init();
		printf("Case #%d:\n",kase);
		scanf("%d",&n);
		int nn = sqrt(maxn);
		int res = 0;
		built_A = built_B = false;
		for(int i=0;i<n;i++){
			scanf("%s",in);
			len = strlen(in)-1;
			int md = res%len;
			for(int j=0;j<len;j++) text[j] = in[(j+md)%(len)+1];
			text[len] = '\0';
			if(in[0]=='+'){
				Aho_B.Insert(text);
				built_B = false;
				if(Aho_B.Size>nn) Aho_A.unity(Aho_B),built_A=false;
			}
			else if(in[0]=='?'){
				if(!built_A){
					built_A = true;
					Aho_A.build_fail();
				}
				if(!built_B){
					built_B = true;
					Aho_B.build_fail();
				}
				res = Aho_A.match(text)+Aho_B.match(text);
				printf("%d\n",res);
			}
		}
	}
	return 0;
}