I was implementing a Trie for Google Kickstart earlier today and the code is malfunctioning in a very strange way. I have no idea why this is happening. I narrowed down the problem in a few hours.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
struct node{
int ends=0;
int child[26]={0};
};
vector<node> trie;
int makenode(){
trie.push_back(node());
int x=(int)trie.size() - 1;
cout<<x<<" ";
return x;
}
void insert(string &s,int root=0,int pos=0){
if(pos==(int)(s.size())){
trie[root].ends++;
return;
}
int next=s[pos]-'A';
if(!trie[root].child[next]){
// trie.push_back(node()); trie[root].child[next]=(int)trie.size()-1; //THIS LINE WORKS FINE
trie[root].child[next]=makenode();
cout<<trie[root].child[next]<<"\n";
}
insert(s,trie[root].child[next],pos+1);
}
int main(){
trie.clear();
trie.push_back(node());
string s;
cin>>s;
insert(s);
return 0;
}
The function makenode() returns x. When I print x, the values are fine but after returning the values are getting changed.
One would expect the above code to print the same integers per line but the values aren't same.
These are the values of x before and after returning from the function makenode().
Does anybody have any idea why this is happening?
(I have noticed that only the values 1,2,4,8,16,32,etc are wrong)