Trie用vectorMLE求条
查看原帖
Trie用vectorMLE求条
1098596
WhiteNight__楼主2024/11/28 11:31
#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 c;
		int t[27];
		Table (int c_ = 0)
		{
			this->c = c_;
			this->isend = false;
			memset (t , 0 , sizeof t);
		}
	};
	vector <Table> tr;
	
	Trie ()
	{
		cnt = 0;
		tr.clear();
		tr.push_back(Table(-1));
	}
	
	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;
//			printf("root = %d  tr.s = %u  cnt = %d\n",root,tr.size(),cnt);
			if(tr.at(root).t[fx] == 0)
			{
				++ cnt;
				tr.push_back(Table(fx));
				tr.at(root).t[fx] = cnt;
			}
			root = tr.at(root).t[fx];
		}
		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;
}
2024/11/28 11:31
加载中...