Logue P2580 so he started the wrong roll call (Trie / dictionary tree)

1, Title Description

Background of topic

XS middle school (Xiaoshan middle school?) The coach of chemistry competition group is a man who loves hearthstone.

He would roll the furnace stone and call the roll so that one day he went to a classmate twice in a row, and then he was discovered by the passing headmaster, and then there was an Euler Euler (for details, please refer to the finished match CON900).

Title Description

After that, the principal appoints you as special agent and records his roll call every day. The headmaster will provide the number and list of the students in the chemistry competition, and you need to tell the headmaster if he has misnamed. Why don't you just let him play with the hearthstone

Input format

The first line is an integer n, indicating the number of people in the class. Next N lines, each line of a string represents its name (different from each other, and only contains lowercase letters, with a length of no more than 50). An integer m in the n+2 line indicates the name of the coach. Next M lines, each line of a string represents the name of the coach report (only lowercase letters, and the length does not exceed 50).

Output format

For each coach's name, output one line. If the name is correct and appears for the first time, output "OK". If the name is WRONG, output "WRONG". If the name is correct but not appears for the first time, output "REPEAT". (no quotes)

Example of input and output

Input #1

5  
a
b
c
ad
acd
3
a
a
e

Output #1

OK
REPEAT
WRONG

Description / tips

For 40% of the data, n ≤ 1000,m ≤ 2000;

For 70% of the data, n ≤ 10000,m ≤ 20000;

For 100% of the data, n ≤ 10000, m ≤ 100000.

T1 always gives points.

2, Description of algorithm analysis

Trie, also known as prefix tree, is a data structure optimized for string matching. The root node is empty, and each node has several pointers to the next node. When querying by string, start from the root node (0 bits have been matched), and each deeper layer represents one more string that has been matched to be searched.


(the two methods are equivalent)
The information carried by the dictionary tree can be saved on the middle non leaf node or the leaf node.
The code given in this paper encapsulates the dictionary tree into a class. Although each node has an unsigned variable named visited to indicate whether the query name has been clicked, only the visited variable on the leaf node has practical significance.

3, AC code

Unordered map

#include<iostream>
#include<unordered_map>
#include<string>
#pragma warning(disable:4996)
using namespace std;
unsigned m, n; unordered_map<string, bool> f; pair<string, bool> p; string name;
int main() {
	cin >> n; ++n; p.first.resize(50);
	while (--n) {
		cin >> p.first; f.emplace(p);
	}
	cin >> m; ++m; unordered_map<string, bool>::iterator I;
	while (--m) {
		cin >> name; I = f.find(name);
		if (I == f.end())puts("WRONG");
		else if (I->second == false) { puts("OK"); I->second = true; }
		else puts("REPEAT");
	}
	return 0;
}

FA Er dictionary tree
In this method, if the map is replaced by unordered map, the time will be increased. The reason is that unordered_map has the complexity of O(1), but its constant is large.
The top and bottom commits change the map of the dictionary tree to unordered_map, and the middle uses the dictionary tree but keeps the map unchanged.

#include<cstdio>
#include<map>
#pragma warning(disable:4996)
class trie {
private:
	struct node { std::map<char, node*> next; unsigned visited = 0; };
	std::map<char, node*>::iterator I; std::pair<char, node*> P;
	node* root;
public:
	trie() { root = new node(); }
	void insert(const char* const k) {
		node* p = root; const char* q = k;
		while (*q != 0) {
			I = p->next.find(*q);
			if (I == p->next.end()) { P.first = *q; P.second = new(node)(); p->next.emplace(P); I = p->next.find(*q); }
			p = I->second, ++q;
		}
	}
	unsigned find(const char* const w) {
		node* p = root; const char* q = w;
		while (*q != 0) {
			I = p->next.find(*q);
			if (I == p->next.end()) { return 2; }
			p = I->second, ++q;
		}
		if (p->visited == 0) { p->visited = 1; return 0; }
		else return 1;
	}
};
trie t; unsigned m, n; char name[51];
int main() {
	scanf("%u", &n);
	for (unsigned i = 0; i < n; ++i) { scanf("%s", name); t.insert(name); }
	scanf("%u", &m);
	for (unsigned i = 0; i < m; ++i) {
		scanf("%s", name);
		switch (t.find(name)) {
		case 0:puts("OK"); continue;
		case 1:puts("REPEAT"); continue;
		default:puts("WRONG");
		}
	}
	return 0;
}
217 original articles published, 20 praised, 10000 visited+
Private letter follow

Posted on Wed, 12 Feb 2020 07:42:37 -0800 by Vasudhevan