#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<set>
#include<algorithm>
using namespace std;
const int N = 26, M = 1000000;
int tot = 0;
struct Trie
{
int next[N];
bool val;
int sum;
void init()
{
memset(next, -1, sizeof(next));
val = false;
}
}Tire[M];
//int c[1000000],maxx=0;
int sum = 0;
void insert(string str)
{
int len = str.length();
int root = 0;
for (int i = 0; i < len; i++)
{
int x = str[i] - 'a';
if (Tire[root].next[x] == -1)
{
Tire[root].next[x] = ++tot;
root = Tire[root].next[x];
Tire[root].init();
}
else
{
root = Tire[root].next[x];
}
//Tire[root].val = false;
}
Tire[root].val = true;
}
bool search(string str)
{
int len = str.length(), root = 0;
for (int i = 0; i < len; i++)
{
int x = str[i] - 'a';
/*if (Tire[root].val == true)
{
return true;
}*/
if (Tire[root].next[x] == -1)
{
return false;
}
else
{
root = Tire[root].next[x];
}
}
return Tire[root].val;
//return true;
}
