When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

dimtim's blog

By dimtim, history, 8 years ago, In English

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'];
	}
}

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it