求助,本地过样例,提交爆RE
查看原帖
求助,本地过样例,提交爆RE
554746
yiming564楼主2024/7/21 19:18

本地的环境使用 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;
}
2024/7/21 19:18
加载中...