BZOJ 2555 SubString 後綴自動機

題目大意：給出一個字符串，支持在線在字符串後面加一個字符串，查詢一個字符串在串中出現過幾次。

思路：如果不想寫正解的話，這個題就是後綴自動機的簡單應用。正解其實是LCT+SAM，但是時間比暴力慢一倍。。。

暴力就很簡單了，正序建立後綴自動機，每次查詢的時候找到位置直接輸出size的值。注意兩點，一個是分裂節點的時候，size也要復制過去。查詢的時候發現找不到要return 0;

CODE：

#include 
#include 
#include 
#include 
#define MAX 4000010
using namespace std;

struct Complex{
	Complex* tranc[26],*father;
	int len,size;
}mempool[MAX],*C = mempool,*last,*root,none,*nil = &none;

Complex *NewComplex(int _)
{
	C->len = _;
	C->size = 0;
	fill(C->tranc,C->tranc + 26,nil);
	C->father = nil;
	return C++;
}

void Initialize()
{
	root = last = NewComplex(0);
}

inline void Add(int c)
{
	Complex *np = NewComplex(last->len + 1),*p = last;
	for(; p != nil && p->tranc[c] == nil; p = p->father)	p->tranc[c] = np;
	if(p == nil)	np->father = root;
	else {
		Complex *q = p->tranc[c];
		if(q->len == p->len + 1)	np->father = q;
		else {
			Complex *nq = NewComplex(p->len + 1);
			memcpy(nq->tranc,q->tranc,sizeof(nq->tranc));
			nq->father = q->father;
			np->father = q->father = nq;
			nq->size = q->size;
			for(; p != nil && p->tranc[c] == q; p = p->father)	p->tranc[c] = nq;
		}
	}
	last = np;
	for(; np != root; np = np->father)
		++np->size;
}

int asks;
char s[MAX],opt[10];

inline void DecodeWithMask(int mask)
{
	int length = strlen(s);
	for(int i = 0; i < length; ++i) {
		mask = (mask * 131 + i) % length;
		swap(s[i],s[mask]);
	}
}

inline int Ask()
{
	Complex *now = root;
	int length = strlen(s);
	for(int i = 0; i < length; ++i)
		if(now->tranc[s[i] - 'A'] != nil)
			now = now->tranc[s[i] - 'A'];
		else	return 0;
	return now->size;
}

int main()
{
	Initialize();
	scanf("%d%s",&asks,s);
	int length = strlen(s);
	for(int i = 0; i < length; ++i)
		Add(s[i] - 'A');
	int mask = 0;
	for(int i = 1; i <= asks; ++i) {
		scanf("%s%s",opt,s);
		DecodeWithMask(mask);
		if(opt[0] == 'Q') {
			int last_ans = Ask();
			printf("%d\n",last_ans);
			mask ^= last_ans;
		}
		else {
			length = strlen(s);
			for(int i = 0; i < length; ++i)
				Add(s[i] - 'A');
		}
	}
	return 0;
}