题目见P2580

MLE提交记录

代码大概是这样的

我也尝试过用数组替换vector，但在数组大小为 $5\times10^5$ 时 8 , 9 RE；在 $6\times10^5$ 时 8 , 9 MLE。但我看其他题解可以用 $5\times10^5$ 过这一道题，并且空间小8倍左右。

#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;
}