一道Bouvardia想出来却没写对的题╥﹏╥…

Table of Contents

  1. Description
  2. Solution

Description

定义一个字符串集合。支持下列操作：

  1. 插入一个字符串。
  2. 查询一个字符串。
  3. 纠缠串S和串T, 使得对于集合中的任何一个串S + A(A可以为空), 有T + A也存在于集合, T + B同理. 这项操作可能会向集合中引入新串, 也有可能引入长度为无限的串.

Solution

前两个操作在Trie上做就好了喵~

观察第三个操作, 一定是两个串共享了后缀, 所以要在Trie树上将它们合并! 不过Bouvardia考场上没能写对, 对于合并的两个节点本身没有考虑太细, 也忽略了复杂度的优化……

Trie树对于每个转移递归合并, 同时用并查集维护每个节点的最终去处.

讲题的老师说这题思路很新颖, 确实呢.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <string>
#include <queue>

using namespace std;

const int maxn = 8e+6 + 5;
const int maxp = 1e+6 + 5; 

struct node
{
	bool tag;
	int nxt[10];
	int fa;
}t[maxp]; int ptr;

int m;
char str[maxn];
//queue<int> trash_bin;

int find(int x) {return x == t[x].fa ? x : t[x].fa = find(t[x].fa);}
inline void Insert(char *s)
{
	int n = strlen(s), now = 0;
	for(int i = 0; i < n; ++i)
	{
		//while(t[now].rep) now = t[now].rep;
		//printf("n>%d\n", now);
		int ch = (s[i] ^ 48);
		if(!t[now].nxt[ch]) 
		{
			t[now].nxt[ch] = ++ptr;
			//else t[now].nxt[ch] = trash_bin.front(), trash_bin.pop();
		}
		now = find(t[now].nxt[ch]);
	}
	//while(t[now].rep) now = t[now].rep;
	//printf("n>%d\n", now);
	t[now].tag = 1;
}
inline int& iInsert(char *s)
{
	int n = strlen(s), now = 0;
	for(int i = 0; i < n - 1; ++i)
	{
		//while(t[now].rep) now = t[now].rep;
		//printf("i>%d\n", now);
		int ch = (s[i] ^ 48);
		if(!t[now].nxt[ch])
		{
			t[now].nxt[ch] = ++ptr;
		}
		now = find(t[now].nxt[ch]);
	}
	//while(t[now].rep) now = t[now].rep;
	//printf("i>%d\n", now);
	return t[now].nxt[(s[n - 1] ^ 48)];
}
void merge(int &x, int &y, bool tag)
{
	x = find(x); int ty = find(y);
	if(!x && !ty)
	{
		if(tag) x = y = ++ptr;
		return;
	}
	else if(x == ty) return;
	if(!x) {x = ty; return;}
	else if(!y) {y = x; return;}
	t[ty].fa = x; t[x].tag |= t[ty].tag;
	for(int i = 0; i < 10; ++i)
	{
		merge(t[x].nxt[i], t[ty].nxt[i], false);
		x = find(x);
	}
}
inline void entangle()
{
	scanf("%s", str);
	int &s1 = iInsert(str); 
	//while(t[s1].rep) s1 = t[s1].rep;
	scanf("%s", str);
	int &s2 = iInsert(str);
	//while(t[s2].rep) s2 = t[s2].rep;
	merge(s1, s2, 1);
}
inline bool query(char *s)
{
	int now = 0, n = strlen(s);
	for(int i = 0; i < n; ++i)
	{
		//while(t[now].rep) now = t[now].rep;
		//printf("q>%d\n", now);
		int ch = (str[i] ^ 48);
		if(!t[now].nxt[ch]) return false;
		now = find(t[now].nxt[ch]);
	}
	//while(t[now].rep) now = t[now].rep;
	//printf("q>%d\n", now);
	return t[now].tag;
}


int main()
{
	freopen("quantum.in", "r", stdin);
	freopen("quantum.out", "w", stdout);
	scanf("%d", &m); int id;
	for(int i = 1; i < maxp; ++i) t[i].fa = i;
	while(m--)
	{
		scanf("%d", &id);
		if(id == 1)
		{
			scanf("%s", str);
			Insert(str);
		}
		else if(id == 2)
		{
			scanf("%s", str);
			printf("%d\n", query(str));
		}
		else
		{
			entangle();
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}