【BZOJ2555】SubString，bzoj2555substring

【BZOJ2555】SubString，bzoj2555substring

【题目链接】

• 点击打开链接
  

【思路要点】

• 补档博客，无题解。

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN	1200005
#define MAXM	3000005
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int mask;
char s[MAXM];
string chars;
void gets(int mask, string &chars) {
	scanf("%s", s);
	chars = s;
	for (unsigned j = 0; j < chars.length(); j++) {
		mask = (mask * 131 + j) % chars.length();
		char t = chars[j];
		chars[j] = chars[mask];
		chars[mask] = t;
	}
}
struct LinkCutTree {
	struct Node {
		int child[2];
		int father, up;
		int value, tag;
	} a[MAXN];
	void modify(int x, int d) {
		a[x].tag += d;
		a[x].value += d;
	}
	void pushdown(int root) {
		if (a[root].tag == 0) return;
		if (a[root].child[0]) modify(a[root].child[0], a[root].tag);
		if (a[root].child[1]) modify(a[root].child[1], a[root].tag);
		a[root].tag = 0;
	}
	bool get(int x) {
		return x == a[a[x].father].child[1];
	}
	void rotate(int x) {
		if (a[x].father == 0) return;
		int f = a[x].father, g = a[f].father;
		bool tnp = get(f), tmp = get(x);
		pushdown(f); pushdown(x);
		a[x].up = a[f].up; a[f].up = 0;
		a[f].child[tmp] = a[x].child[tmp ^ 1];
		a[a[x].child[tmp ^ 1]].father = f;
		a[x].child[tmp ^ 1] = f;
		a[f].father = x;
		a[x].father = g;
		if (g) a[g].child[tnp] = x;
	}
	void splay(int x) {
		pushdown(x);
		for (int f = a[x].father; (f = a[x].father); rotate(x))
			if (get(f) == get(x)) rotate(f);
			else rotate(x);
	}
	void access(int x) {
		splay(x);
		int tmp = a[x].child[1];
		a[tmp].father = 0;
		a[tmp].up = x;
		a[x].child[1] = 0;
		while (a[x].up) {
			int f = a[x].up;
			splay(f);
			tmp = a[f].child[1];
			a[tmp].father = 0;
			a[tmp].up = f;
			a[f].child[1] = x;
			a[x].father = f;
			a[x].up = 0;
			splay(x);
		}
	}
	void link(int x, int f) {
		access(x);
		splay(x);
		access(f);
		splay(f);
		modify(f, a[x].value);
		pushdown(f);
		a[f].child[1] = x;
		a[x].father = f;
	}
	void cut(int x) {
		access(x);
		splay(x);
		int f = a[x].child[0];
		a[x].child[0] = 0;
		a[f].father = 0;
		modify(f, -a[x].value);
	}
	void value(int x) {
		access(x);
		splay(x);
		modify(x, 1);
	}
	int query(int x) {
		access(x);
		splay(x);
		return a[x].value;
	}
} LCT;
struct SuffixAutomaton {
	int child[MAXN][26];
	int father[MAXN], depth[MAXN];
	int root, size, last;
	int new_node(int dep) {
		depth[size] = dep;
		return size++;
	}
	void Extend(int ch) {
		int p = last, np = new_node(depth[p] + 1);
		while (child[p][ch] == 0) {
			child[p][ch] = np;
			p = father[p];
		}
		if (child[p][ch] == np) {
			father[np] = root;
			LCT.link(np, root);
		} else {
			int q = child[p][ch];
			if (depth[p] + 1 == depth[q]) {
				father[np] = q;
				LCT.link(np, q);
			} else {
				int nq = new_node(depth[p] + 1);
				while (child[p][ch] == q) {
					child[p][ch] = nq;
					p = father[p];
				}
				LCT.cut(q);
				father[nq] = father[q];
				LCT.link(nq, father[q]);
				father[q] = nq;
				LCT.link(q, nq);
				father[np] = nq;
				LCT.link(np, nq);
				memcpy(child[nq], child[q], sizeof(child[q]));
			}
		}
		last = np;
		LCT.value(np);
	}
	void push_back(string &chars) {
		for (unsigned i = 0; i < chars.size(); i++)
			Extend(chars[i] - 'A');
	}
	void init() {
		size = 1;
		root = last = new_node(0);
		father[root] = root;
		scanf("\n%s", s);
		chars = s;
		push_back(chars);
	}
	int query(string &chars) {
		int now = root;
		for (unsigned i = 0; i < chars.size(); i++)
			now = child[now][chars[i] - 'A'];
		if (now == 0) return 0;
		else return LCT.query(now);
	}
} SAM;
int main() {
	int q; read(q);
	SAM.init();
	while (q--) {
		char opt[15];
		scanf("\n%s", opt);
		gets(mask, chars);
		if (opt[0] == 'A') SAM.push_back(chars);
		else {
			int ans = SAM.query(chars);
			printf("%d\n", ans);
			mask ^= ans;
		}
	}
	return 0;
}