【luogu P2580】【Trie樹】于是他錯誤的點名開始了

于是他錯誤的點名開始了

題目連結：luogu P2580

題目大意

有一堆字元串，然後有一些詢問，每次給你一個字元串，如果那一堆字元串裡面沒有這個字元串，就輸出 WRONG，如果問的不是第一次，就輸出 REPEAT，否則輸出 OK。

思路

這道題主要就是 Trie 樹的模闆題。

主要就是一個點會有一些兒子，代表它接下來的下一個字元是哪個。

當然，這個點自己也會代表一個字元。（深度就代表它是在第幾位的）

一個從根節點到一個點形成的鍊的每個點代表的資訊組合起來，就形成了一個字元串。

那我們在這個字元串的最後一個點可以記錄它的出現，以及出現的次數，以及題目要求的東西。

代碼

#include<cstdio>
#include<cstring>

using namespace std;

struct Trie {
	int son[26], end, point;
}trie[1000001];
int n, m, cn, now, KK, re, op;
char c[100001];

void build() {
	now = 0;
	for (int i = 0; i < cn; i++) {
		if (!trie[now].son[c[i] - 'a']) {
			trie[now].son[c[i] - 'a'] = ++KK;
		}
		now = trie[now].son[c[i] - 'a'];
	}
	trie[now].end++;//記錄是否有這個字元串
}

int find() {
	now = 0;
	re = 0;
	for (int i = 0; i < cn; i++) {
		if (!trie[now].son[c[i] - 'a']) return 0;//已經确定沒有這個字元串，直接是 WRONG
		
		now = trie[now].son[c[i] - 'a'];
	}
	trie[now].point++;//記錄詢問的次數
	return now;
}

int main() {
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++) {
		scanf("%s", c);
		cn = strlen(c);
		
		build();
	}
	
	scanf("%d", &m);
	
	for (int i = 1; i <= m; i++) {
		scanf("%s", c);
		cn = strlen(c);
		
		op = find();
		if (!trie[op].end) printf("WRONG\n");
			else if (trie[op].point > 1) printf("REPEAT\n");
				else printf("OK\n");
	}
	
	return 0;
}