struct TrieTree {
int n, root;
int MAX, ALPHABET;
vector<vector<int> > next;
vector<int> data;
void init(int MAX, int ALPHABET) {
root = 0, n = 1; data[root] = 0;
next.resize(MAX);
for(int i = 0; i < MAX; ++i){
next[i].resize(ALPHABET);
for(int j = 0; j < ALPHABET; ++j)
next[i][j] = -1;
}
data.resize(MAX);
}
void insert(char *s) {
int curr = root, i, k;
for(i = 0; s[i]; i++) {
k = s[i]-'a';
if(next[curr][k] == -1) {
next[curr][k] = n;
data[n] = s[i]; // optional
for(int j = 0; j < ALPHABET;++j)
next[n][j]=-1;
n++;
}
curr = next[curr][k];
}
data[curr] = 0; // sentinel, optional
}
bool find(char *s) {
int curr = root, i, k;
for(i = 0; s[i]; i++) {
k = s[i]-'a';
if(next[curr][k] == -1) return false;
curr = next[curr][k];
}
return (data[curr] == 0);
}
};