字符串 - Trie
Trie Ref:OI Wiki
示例代码:
struct trie {
int nex[100000][26], cnt;
bool exist[100000]; // 该结点结尾的字符串是否存在
void insert(char *s, int l) { // 插入字符串
int p = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!nex[p][c]) nex[p][c] = ++cnt; // 如果没有,就添加结点
p = nex[p][c];
}
exist[p] = 1;
}
bool find(char *s, int l) { // 查找字符串
int p = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!nex[p][c]) return 0;
p = nex[p][c];
}
return exist[p];
}
};
题目: P2580 于是他错误的点名开始了
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
char s[60];
int n, m, ch[N][26], tag[N], tot = 1;
int main() {
cin>>n;
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
int u = 1;
for (int j = 1; s[j]; ++j) {
int c = s[j] - 'a';
if (!ch[u][c])
ch[u][c] = ++tot;
u = ch[u][c];
}
tag[u] = 1;
}
scanf("%d", &m);
while (m--) {
scanf("%s", s + 1);
int u = 1;
for (int j = 1; s[j]; ++j) {
int c = s[j] - 'a';
u = ch[u][c];
if (!u)
break; // 不存在对应字符的出边说明名字不存在
}
if (tag[u] == 1) {
tag[u] = 2;
puts("OK");
} else if (tag[u] == 2)
puts("REPEAT");
else
puts("WRONG");
}
return 0;
}
respond-post-13
gjgj
\