GRE Words Revenge
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 327680/327680 K (Java/Others)
Total Submission(s): 2693 Accepted Submission(s): 668
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
题目链接：HDU 4787
用平方分割的优化技巧，建立两个$AC$自动机，先把所有字符往小的自动机里放，当小的自动机字符数大于$\sqrt{N}$的时候将小的和大的合并，然后清空小的；询问的时候输出两个自动机的答案和即可。主要学到的就是如何把两个$AC$自动机合并，$BFS$,$DFS$均可。
代码: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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
const int M = 5e6 + 7;
char s[M], t[M];
struct ac
{
struct Trie
{
int nxt[2], fail, v;
void init()
{
nxt[0] = nxt[1] = 0;
fail = 0;
v = 0;
}
} L[N];
int sz;
void init()
{
sz = 0;
L[sz++].init();
}
inline int newnode()
{
L[sz].init();
return sz++;
}
void ins(char s[], int len)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
int v = s[i] - '0';
if (!L[u].nxt[v])
L[u].nxt[v] = newnode();
u = L[u].nxt[v];
}
L[u].v = 1;
}
void build()
{
queue<int>Q;
L[0].fail = 0;
for (int i = 0; i < 2; ++i)
{
int v = L[0].nxt[i];
if (v)
Q.push(v);
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = 0; i < 2; ++i)
{
int v = L[u].nxt[i];
if (v)
{
Q.push(v);
int t = L[u].fail;
while (t && !L[t].nxt[i])
t = L[t].fail;
L[v].fail = L[t].nxt[i];
}
}
}
}
int query(char s[], int len)
{
int u = 0, ret = 0;
for (int i = 0; i < len; ++i)
{
int v = s[i] - '0';
while (u && !L[u].nxt[v])
u = L[u].fail;
u = L[u].nxt[v];
int t = u;
while (t)
{
if (L[t].v)
++ret;
t = L[t].fail;
}
}
return ret;
}
int exist(char s[], int len)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
u = L[u].nxt[s[i] - '0'];
if (!u)
return 0;
}
return L[u].v;
}
} big, small;
void Merge()
{
queue<int>Q;
Q.push(0);
Q.push(0);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
int v = Q.front();
Q.pop();
big.L[u].v |= small.L[v].v;
for (int i = 0; i < 2; ++i)
{
if (small.L[v].nxt[i])
{
if (!big.L[u].nxt[i])
big.L[u].nxt[i] = big.newnode();
Q.push(big.L[u].nxt[i]);
Q.push(small.L[v].nxt[i]);
}
}
}
big.build();
small.init();
}
void Move(int k, int len)
{
for (int i = 0; i < len; ++i)
s[i] = t[(i + k) % len];
}
int main(void)
{
int TC, n;
scanf("%d", &TC);
for (int q = 1; q <= TC; ++q)
{
big.init();
small.init();
scanf("%d", &n);
printf("Case #%d:\n", q);
int ans = 0;
while (n--)
{
char c;
scanf(" %c%s", &c, t);
int len = strlen(t);
Move(ans, len);
if (c == '+')
{
if (small.exist(s, len) || big.exist(s, len))
continue;
small.ins(s, len);
small.build();
if (small.sz > 316)
Merge();
}
else
printf("%d\n", ans = small.query(s, len) + big.query(s, len));
}
}
return 0;
}