### dimtim's blog

By dimtim, history, 3 years ago, ,

I saw a codeforces submission, where the coder built Trie using 2d array. I have understood the code. But now I want to use this method and make it generic. I do not see end of word marker in this code.

Ex: Let us say there are 'ab','abc'. Now, how can I know where is the word boundary. What is the modification that I need to make in order to mark the end of the word.

const int MAXN = 1e5 + 20;

int n, k;
int tr[MAXN][28], sz;

void insert(string t){
int cur = 0;
for (int i = 0; i < t.size(); i++){
if (tr[cur][t[i] - 'a'] == 0)
tr[cur][t[i] - 'a'] = ++sz;
cur = tr[cur][t[i] - 'a'];
}
}


• -5

 » 3 years ago, # |   0 use array of pair or structure.Try to mark the end of word variable in those cell if it is the end of word.
 » 3 years ago, # |   0 I am not understanding why the down-votes to this question? The OP just wanted to understand how the end of word is marked in this implementation of trie. Seems like a legitimate and honest question and a urge to learn. OP looks like a beginner like me, hence the mutual feeling.
 » 5 months ago, # | ← Rev. 4 →   -8 //Full code implementation of trie using the 2d array for find string in Dictionary ** const int N = 1e5 + 100; int n, k, nxt = 1; vii Node(N,vi(27,-1)); bool win[N], los[N]; //string s[N];void build(string s,int num){ int i=0,v=0; for(int i=0;i=s.size()){ cout<<"find"<>n>>t; while(n--){ string s; int num; cin>>s>>num; build(s,num); } while(t--){ string s; cin>>s; search(s); } return 0;`}**