BZOJ 3881 COCI 2015 Divljak

题面

Description

Tom有n个字符串S1,S2...Sn，Jerry有一个字符串集合T，一开始集合是空的。

接下来会发生q个操作，操作有两种形式：

“1 P”，Jerry往自己的集合里添加了一个字符串P。

“2 x”，Tom询问Jerry，集合T中有多少个字符串包含串Sx。（我们称串A包含串B，当且仅当B是A的子串）

Jerry遇到了困难，需要你的帮助。

Input

第1行，一个数n；

接下来n行，每行一个字符串表示Si；

下一行，一个数q；

接下来q行，每行一个操作，格式见题目描述。

Output

对于每一个Tom的询问，帮Jerry输出答案。

Sample Input

3

a

bc

abc

5

1 abca

2 1

1 bca

2 2

2 3

Sample Output

HINT

100%: \(1≤N,Q≤100000\), \(\sum_{s \in S} |s|, \sum_{s \in T}|s| \le 2 \times 10^6\), \(alphabet = \{a ... z\}\)

Solution

正解貌似是fail树加树链的并, 但我写的是后缀树. 还没读入完空间就炸了... 先放一份代码吧

#include <cstdio>

#include <cstring>

#include <vector>

#define vector std::vector

const int LEN = (int)2e6, N = (int)1e5, Q = (int)1e5;

int q;

int ans[Q];

struct segmentTree

{

	struct node

	{

		node *suc[2];

		int sz;

		inline node() {for(int i = 0; i < 2; ++ i) suc[i] = NULL; sz = 0;}

	}*rt;

	inline segmentTree() {rt = NULL;}

	node* insert(node *u, int L, int R, int pos)

	{

		if(u == NULL) u = new node;

		if(L == R) {u->sz = 1; return u;}

		if(pos <= L + R >> 1) u->suc[0] = insert(u->suc[0], L, L + R >> 1, pos); else u->suc[1] = insert(u->suc[1], (L + R >> 1) + 1, R, pos);

		u->sz = 0;

		for(int i = 0; i < 2; ++ i) if(u->suc[i] != NULL) u->sz += u->suc[i]->sz;

		return u;

	}

	inline void insert(int pos) {rt = insert(rt, 1, q, pos);}

	int query(node *u, int L, int R, int pos)

	{

		if(u == NULL) return 0;

		if(R <= pos) return u->sz;

		return query(u->suc[0], L, L + R >> 1, pos) + (pos > L + R >> 1 ? query(u->suc[1], (L + R >> 1) + 1, R, pos) : 0);

	}

	inline int query(int pos) {return query(rt, 1, q, pos);}

	node* merge(int L, int R, node *u, node *_u)

	{

		if(u == NULL) return _u; if(_u == NULL) return u;

		if(L == R) {u->sz |= _u->sz; delete _u; return u;}

		u->suc[0] = merge(L, L + R >> 1, u->suc[0], _u->suc[0]); u->suc[1] = merge((L + R >> 1) + 1, R, u->suc[1], _u->suc[1]);

		delete _u;

		u->sz = 0;

		for(int i = 0; i < 2; ++ i) if(u->suc[i] != NULL) u->sz += u->suc[i]->sz;

		return u;

	}

	inline void merge(segmentTree *T) {rt = merge(1, q, rt, T->rt);}

};

struct suffixAutomaton

{

	struct node

	{

		node *suc[26], *pre;

		int len;

		vector<int> bck, qry;

		int vst;

		vector<node*> successorOnSuffixTree;

		inline node() {for(int i = 0; i < 26; ++ i) suc[i] = NULL; pre = NULL; vst = 0; bck.clear(); qry.clear(); successorOnSuffixTree.clear();}

	}*rt;

	inline suffixAutomaton() {rt = new node; rt->len = 0;}

	inline node* insert(char *str, int len, int id)

	{

		node *lst = rt;

		for(int i = 0; i < len; ++ i)

		{

			int c = str[i] - 'a';

			if(lst->suc[c] != NULL)

			{

				node *p = lst->suc[c];

				if(p->len == lst->len + 1) { if(~ id) p->bck.push_back(id); lst = p; continue;}

				node *q = new node; if(~ id) q->bck.push_back(id);

				for(int i = 0; i < 26; ++ i) q->suc[i] = p->suc[i]; q->pre = p->pre; q->len = lst->len + 1;

				p->pre = q;

				for(; lst != NULL && lst->suc[c] == p; lst = lst->pre) lst->suc[c] = q;

				lst = q;

				continue;

			}

			node *u = new node; u->len = lst->len + 1; if(~ id) u->bck.push_back(id);

			for(; lst != NULL && lst->suc[c] == NULL; lst = lst->pre) lst->suc[c] = u;

			if(lst == NULL) u->pre = rt;

			else

			{

				node *p = lst->suc[c];

				if(p->len == lst->len + 1) u->pre = p;

				else

				{

					node *q = new node; for(int i = 0; i < 26; ++ i) q->suc[i] = p->suc[i]; q->pre = p->pre; q->len = lst->len + 1;

					u->pre = p->pre = q;

					for(; lst != NULL && lst->suc[c] == p; lst = lst->pre) lst->suc[c] = q;

				}

			}

			lst = u;

		}

		return lst;

	}

	void build(node *u)

	{

		u->vst = 1; if(u->pre != NULL) u->pre->successorOnSuffixTree.push_back(u);

		for(int i = 0; i < 26; ++ i) if(u->suc[i] != NULL && ! u->suc[i]->vst) build(u->suc[i]);

	}

	inline void buildSuffixTree() {build(rt);}

	segmentTree* DFS(node *u)

	{

		segmentTree *seg = new segmentTree;

		for(auto id : u->bck) seg->insert(id);

		for(auto v : u->successorOnSuffixTree)

		{

			segmentTree *res = DFS(v);

			seg->merge(res);

		}

		for(auto qry : u->qry) ans[qry] = seg->query(qry);

		return seg;

	}

	inline void work() {DFS(rt);}

}SAM;

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("davljak.in", "r", stdin);

	freopen("davljak.out", "w", stdout);

	#endif

	int n; scanf("%d\n", &n);

	static char str[LEN];

	static suffixAutomaton::node *ed[N + 1];

	for(int i = 1; i <= n; ++ i) scanf("%s", str), ed[i] = SAM.insert(str, strlen(str), -1);

	scanf("%d", &q);

	for(int i = 1; i <= q; ++ i)

	{

		int opt; scanf("%d ", &opt);

		if(opt == 1) scanf("%s", str), SAM.insert(str, strlen(str), i);

		else if(opt == 2)

		{

			int x; scanf("%d", &x);

			ed[x]->qry.push_back(i);

		}

	}

	SAM.buildSuffixTree();

	memset(ans, -1, sizeof(ans));

	SAM.work();

	for(int i = 1; i <= q; ++ i) if(~ ans[i]) printf("%d\n", ans[i]);

}

巴特西