本地的环境使用 gcc 11.4.0 / Windows Subsystem Linux,并通过 ulimit set unlimited 解禁了栈空间,在 Remote Judge 上第一个数据点(样例)就 RE,无法复现,求调
// binary group to build AC AM
#include <bits/extc++.h>
#define offset(x) ((x) - 'a')
#define child(node, ch) (next[(node)][offset((ch))])
int m, op;
char str[300005];
class ACAM
{
public:
int next[300005][26], fail[300005], count[300005], w[300005], top;
std::vector<std::string> history;
inline int size() const { return history.size(); }
inline int insert(int &x) { return x ? x : (x = top++); }
inline void insert(const char *str)
{
history.push_back(str);
int u = 0;
for (int i = 0; str[i]; i++)
u = insert(child(u, str[i]));
count[u]++;
}
std::queue<int> q;
inline void build()
{
for (auto ch = 'a'; ch <= 'z'; ch++)
if (child(0, ch))
{
fail[child(0, ch)] = 0;
q.push(child(0, ch));
}
while (!q.empty())
{
auto u = q.front();
q.pop();
w[u] = w[fail[u]] + count[u];
for (char ch = 'a'; ch <= 'z'; ch++)
if (child(u, ch))
{
fail[child(u, ch)] = child(fail[u], ch);
q.push(child(u, ch));
}
else
child(u, ch) = child(fail[u], ch);
}
}
int query(const char *str)
{
int ans = 0, u = 0;
for (auto ch = str; *ch != '\0'; ch++)
ans += w[u = child(u, *ch)];
return ans;
}
ACAM() : top(1) {}
};
class version
{
public:
std::vector<ACAM> root;
void insert(const char *str)
{
ACAM tmp;
root.push_back(tmp);
int size = root.size();
root[size - 1].insert(str);
if (size < 2 || root[size - 2].size() != root[size - 1].size())
root[size - 1].build();
while (size >= 2 && root[size - 2].size() == root[size - 1].size())
{
ACAM new_root;
for (auto &&str : root[size - 1].history)
new_root.insert(str.c_str());
for (auto &&str : root[size - 2].history)
new_root.insert(str.c_str());
new_root.build();
root.pop_back();
root.pop_back();
root.push_back(new_root);
size--;
}
}
int query(const char *str)
{
int ans = 0;
int size = root.size();
for (int i = 0; i < size; i++)
ans += root[i].query(str);
return ans;
}
};
version pos, neg;
int main()
{
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
scanf("%d %s", &op, str);
if (op == 1)
pos.insert(str);
else if (op == 2)
neg.insert(str);
else
{
int pos_total = pos.query(str), neg_total = neg.query(str);
printf("%d\n", pos_total - neg_total);
fflush(stdout);
}
}
return 0;
}