dimtim's blog

By dimtim, history, 3 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'];
	}
}
 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 4   Vote: I like it -8 Vote: I do not like it

//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();i++){
    int t=s[i]-'a';
    if(Node[v][t]==-1){
        Node[v][t]=nxt;
        v=nxt;
        nxt++;
    }
    else{
        v=Node[v][t];
    }

}

}

void search(string s){ int count=0; int v=0,t=s[count]-'a';

while(Node[v][t]!=-1 and count<s.size()){
    v=Node[v][t];
    if(count+1<s.size())
        t=s[count+1]-'a';
    count++;
}

if(count>=s.size()){
    cout<<"find"<<endl;
}
else{
    cout<<"not find"<<endl;
}

}

int main() { ios_base::sync_with_stdio(false); int n,t; cin>>n>>t; while(n--){ string s; int num; cin>>s>>num;
build(s,num); } while(t--){ string s; cin>>s; search(s); }

return 0;

}

**