社区讨论

关于Trie的空间问题

学术版参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@m40vbmly
此快照首次捕获于
2024/11/28 13:22
去年
此快照最后确认于
2025/11/04 13:45
4 个月前
查看原帖
代码大概是这样的
我也尝试过用数组替换vector,但在数组大小为 5×1055\times10^5 时 8 , 9 RE;在 6×1056\times10^5 时 8 , 9 MLE。但我看其他题解可以用 5×1055\times10^5 过这一道题,并且空间小8倍左右。
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int n , m;

struct Trie {
	int cnt;
	struct Table {
		bool isend;
		int t[27];
		Table ()
		{
			this->isend = false;
			memset (t , 0 , sizeof t);
		}
	};
	
	vector <Table> tr;
	
	Trie ()
	{
		cnt = 0;
		tr.clear();
		tr.push_back(Table());
	}
	
	void Insert (string x)
	{
		int lenx = x.size();
		int root(0);
		for(int i = 0 ; i < lenx ; i ++)
		{
			int fx = x.at(i) - 'a' + 1;
			if(tr.at(root).t[fx] == 0)
			{
				++ cnt;
				tr.push_back(Table());
				tr.at(root).t[fx] = cnt;
			}
			root = tr.at(root).t[fx];
//			printf("root = %d  tr.s = %d  cnt = %d\n",root,(int)tr.size(),cnt);
		}
		tr.at(root).isend = true;
	}
	
	bool Find (string x)
	{
		int lenx = x.size();
		int root(0);
		for(int i = 0 ; i < lenx ; i ++)
		{
			int fx = x.at(i) - 'a' + 1;
			if(tr.at(root).t[fx] == 0) return false;
			root = tr.at(root).t[fx];
		}
		return tr.at(root).isend;
	}
}in , pd;

int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; i ++)
	{
		string s;
		cin >> s;
		in.Insert (s);
	}
	scanf("%d",&m);
	for(int i = 1 ; i <= m ; i ++)
	{
		string s;
		cin >> s;
		if(in.Find(s) == false)
		{
			printf("WRONG\n");
		}
		else
		{
			if(pd.Find(s) == false)
			{
				printf("OK\n");
			}
			else printf("REPEAT\n");
		}
		pd.Insert(s);
	}
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...