Topic background

The coach of XS middle school chemistry competition team is a person who loves hearthstone.

He would roll the roll while rubbing the stove stone, so that one day he called a classmate twice in a row, and then he was just found by the passing headmaster, and then there was an EULA EULA (for details, see the concluded game CON900).

Title Description

After that, the headmaster appointed you as a special agent and recorded his roll call every day. The headmaster will provide the number and list of students in the chemistry competition, and you need to tell the headmaster if he has the wrong name. (why not just let him play with hearthstone.)

Input format

The first line is an integer {nn, which indicates the number of people in the class.

Next, there are # nn # lines, and a string in each line represents its name (different from each other, and only contains lowercase letters, and the length does not exceed # 5050).

Line ＾ n+2n+2 ＾ is an integer ＾ mm, which indicates the number of names reported by the coach.

Next, there are # lines, and a string in each line represents the name of the coach newspaper (only lowercase letters, and the length does not exceed # 5050).

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 does not appear for the first time, output ， REPEAT.

Sample input and output

Enter #1 copy

5  
a
b
c
ad
acd
3
a
a
e

Output #1 copy

OK
REPEAT
WRONG

Description / tips

• For data of ﹤ 40 \% 40%, n\le 1000n ≤ 1000, m\le 2000m ≤ 2000.
• For 70 \% 70% data, n\le 10^4n ≤ 104, m\le 2\times 10^4m ≤ 2 × 104.
• For 100 \% 100% data, n\le 10^4n ≤ 104, m ≤ 10^5m ≤ 105.

Done with the hash algorithm, it is inserted and searched twice, and the second time is nested in the first time.

Instead of talking nonsense, go directly to the AC code (there are always only WRONG and REPEAT. After repeated changes for a long time, it is found that the position of the insert function is misplaced and a lot of time is wasted. I always think the code is too long and repeated too much. I will optimize it tomorrow):

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;


/*--------------------------------------------------------------------------------------------------------------*/

typedef struct Node
{
	char *str;
	struct Node *next;
}Node;

typedef struct HashTable
{
	Node **data;//Array of chain header addresses 
	int size;//Size of hash table 
}HashTable;

Node *init_node(char *str,Node *head)//Head insertion 
{
	Node *p = (Node *)malloc(sizeof(Node));//First declare a local variable p 
	p->str = strdup(str);//strdup applies for a new storage space, copies the contents of str to the new storage space, and returns the address of the new storage space 
	p->next = head;
	return p;
}
 
HashTable *init_hashtable(int n)
{
	HashTable *h = (HashTable *)malloc(sizeof(HashTable));
	h->size = n << 1;
	h->data = (Node **)calloc(sizeof(Node *),h->size);
	return h;
}

int BKDRhash(char *str)
{
	int seed = 31 , hash = 0;
	for(int i=0;str[i];i++) hash=hash*seed+str[i];
	return hash & 0x7fffffff;//To ensure a positive value is returned 
}

int insert(HashTable *h,char *str)//insert 
{
	int hash = BKDRhash(str);
	int ind = hash % h->size;
	h->data[ind] = init_node(str,h->data[ind]);
	return 1;
}//Zipper method

int search(HashTable *h,char *str)//lookup 
{
	int hash = BKDRhash(str);
	int ind = hash % h->size;
	Node *p = h->data[ind];
	while(p && strcmp(p->str,str)) p = p->next;
	return p!=NULL;
}

/*-------------------------------------------------------------------------------------------------------*/

typedef struct node
{
	char *str;
	struct node *next;
}node;

typedef struct hashtable
{
	node **data;//Array of chain header addresses 
	int size;//Size of hash table 
}hashtable;

node *init_node2(char *str,node *head)//Head insertion 
{
	node *q = (node *)malloc(sizeof(node));//First declare a local variable p 
	q->str = strdup(str);//strdup applies for a new storage space, copies the contents of str to the new storage space, and returns the address of the new storage space 
	q->next = head;
	return q;
}
 
hashtable *init_hashtable2(int n)
{
	hashtable *h2 = (hashtable *)malloc(sizeof(hashtable));
	h2->size = n << 1;
	h2->data = (node **)calloc(sizeof(node *),h2->size);
	return h2;
}

int BKDRhash2(char *str)
{
	int seed = 31 , hash = 0;
	for(int i=0;str[i];i++) hash=hash*seed+str[i];
	return hash & 0x7fffffff;//To ensure a positive value is returned 
}

int insert2(hashtable *h2,char *str)//insert 
{
	int hash = BKDRhash2(str);
	int ind = hash % h2->size;
	h2->data[ind] = init_node2(str,h2->data[ind]);
	return 1;
}//Zipper method

int search2(hashtable *h2,char *str)//lookup 
{
	int hash = BKDRhash2(str);
	int ind = hash % h2->size;
	node *q = h2->data[ind];
	while(q && strcmp(q->str,str)) q = q->next;
	return q!=NULL;
}

/*-------------------------------------------------------------------------------------------------------*/
char s1[10010][55],s2[100010][55];
int main()
{
	HashTable *h = init_hashtable(10010);
	hashtable *h2 = init_hashtable2(10010);
	
	int n;//Number of people in class 
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s1[i];
		insert(h,s1[i]);
	}
	
	int m;//Number of names reported by the coach 
	cin>>m;
	for(int i=0;i<m;i++)
	{
		cin>>s2[i];
		int k=search(h,s2[i]);
		if(k==0)
			cout<<"WRONG"<<endl;
		else
		{
			int k=search2(h2,s2[i]);
			insert2(h2,s2[i]);
			if(k==1)
				cout<<"REPEAT"<<endl;
			else
				cout<<"OK"<<endl;
		}
	}
	
}

RE is because the second array is turned down.