当前位置: 代码迷 >> 综合 >> 【模板·字典树(trie)】 洛谷2580 于是他错误的点名开始了
  详细解决方案

【模板·字典树(trie)】 洛谷2580 于是他错误的点名开始了

热度:73   发布时间:2023-12-06 08:39:17.0

题目:于是他错误的点名开始了

 

思路:trie树模板。

 

代码:

 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;struct Trie {int ch[300000][30];int in[300000];int sz;void clear(){sz=0;memset(ch[sz],0,sizeof(ch[sz]));memset(in,0,sizeof(in));}void insert(char* x) {int u=0;int len=strlen(x);for(int i=0; i<len; i++) {int y=x[i]-'a';if(!ch[u][y]) {ch[u][y]=++sz;memset(ch[sz],0,sizeof(ch[sz]));}u=ch[u][y];}}int find(char* x) {int u=0;int Len=strlen(x);for(int i=0; i<Len; i++) {int y=x[i]-'a';if(!ch[u][y]) return -1;u=ch[u][y];}in[u]++;return in[u];}
};int n,m;
Trie trie;int main() {trie.clear();scanf("%d",&n);while(n--){char x[100];scanf("%s",x);trie.insert(x);		}scanf("%d",&m);while(m--){char x[100];scanf("%s",x);int y=trie.find(x);if(y==-1) printf("WRONG\n");else if(y==1) printf("OK\n");else printf("REPEAT\n");}return 0;
}