就是把字符串转变成一个树，每个节点连接下一个字符，用空间换时间。
对于区分大小写或不区分的题目，只需要改变 ch[][26]
的值就行了。
ch[u][x] 表示 u 节点（标号决定）下一个
x 字符节点的标号。
如果题目让记录附加值，那就用 val[]
在插入时记录一下就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2333;
struct trie{
ll ch[maxn][26],siz,val[maxn];
trie(){
siz=1;
memset(ch[0],0,sizeof(ch[0]));
memset(val,0,sizeof(val));
}
inline ll idx(char c){return c-'a';}
void insert(char *s,ll v)
{
ll u=0,len=strlen(s+1);
for(ll i=1;i<=len;i++){
ll c=idx(s[i]);
if(!ch[u][c]){
memset(ch[siz],0,sizeof ch[siz]);
val[siz]=0;
ch[u][c]=siz++;
}
u=ch[u][c];
}
val[u]=v;
}
ll query(char *s)
{
ll u=0,len=strlen(s+1);
for(ll i=1;i<=len;i++){
ll c=idx(s[i]);
if(!ch[u][c])return -1;
u=ch[u][c];
}
return val[u];
}
}tr;
int main()
{
return 0;
}
|
（名字好奇怪）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10005*50;
int n;
struct trie
{
int cnt,ch[maxn][26];
int vis[maxn];
trie()
{
cnt=1;
memset(ch[0],0,sizeof ch[0]);
memset(vis,0,sizeof vis);
}
inline int ex(char c){return c-'a';}
inline void insert(char *s)
{
int u=0,len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int c=ex(s[i]);
if(!ch[u][c]){
memset(ch[cnt],0,sizeof ch[cnt]);
ch[u][c]=cnt++;
}
u=ch[u][c];
}
}
inline int query(char *s)
{
int u=0,len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int c=ex(s[i]);
if(!ch[u][c])return 2;
u=ch[u][c];
}
if(!vis[u]){
vis[u]++;return 1;
}
return 3;
}
}tr;
int main()
{
scanf("%d",&n);
char a[100];
for(int i=1;i<=n;i++)
{
scanf("%s",a+1);
tr.insert(a);
}
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",a+1);
switch(tr.query(a))
{
case(1):{
printf("OK\n");
break;
}
case(2):{
printf("WRONG\n");
break;
}
case(3):{
printf("REPEAT\n");
break;
}
}
}
return 0;
}
|
