포(인터)알못인데 아무리 검색해도 배열로 된 트라이 코드가 잘 안 나와서 직접 짠 거 올려봅니다.
먼가 난잡한데 그래도 뿌듯해하며 업로드~~ (사실 문제 안 풀어서 글 쓸 게 없어서 이런 거라도 올림니다 ㅎㅅㅎ
itrie와 ilen, dtrie와 dlen 각각 insert_trie 및 find_trie의 매개변수...?입니당
문자열 매개변수로 주고받는거 잘 못해서 그냥 전역으로 짰... ㅌㅌ
|
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
|
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct trie{
int Go[27];
int output;
}trie_tree[6000001];
int tn=0; //root = 0
string itrie; int ilen;
void insert_trie(int a,int s){//a
if(s==ilen){
trie_tree[a].output = 1;
return;
}
if(trie_tree[a].Go[itrie[s]-'a']==0){
trie_tree[a].Go[itrie[s]-'a'] = ++tn; trie_tree[tn].output=0;
insert_trie(tn,s+1);
} else {
insert_trie(trie_tree[a].Go[itrie[s]-'a'],s+1);
}
return;
}
string dtrie; int dlen;
int find_trie(int a,int s){//a에서 s번째 문자 찾기
if(s==dlen) return trie_tree[a].output;
if(trie_tree[a].Go[dtrie[s]-'a']==0){
return 0;
} else {
return find_trie(trie_tree[a].Go[dtrie[s]-'a'],s+1);
}
}
int N,M,ans=0; string ipt;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin>>N>>M;
trie_tree[0].output=0;
for(int i=1;i<=N;i++){
cin>>ipt;
itrie=ipt; ilen=itrie.length();
insert_trie(0,0);
}
for(int i=1;i<=M;i++){
cin>>ipt;
dtrie=ipt; dlen=dtrie.length();
ans+=find_trie(0,0);
}
cout<<ans;
}
|
cs |