#include
#include<unordered_map>
using namespace std;
class node
{
public:
char data;
bool terminal;
unordered_map<char,node*> children;
int wordcount;
node(char data)
{
this->data=data;
terminal=false;
wordcount=0;
}
};
class trie
{
public:
noderoot;
trie()
{
root=new node(’\0’);
}
void insert(char w)
{
nodetemp=root;
temp->wordcount+=1;
for(int i=0;w[i]!=’\0’;i++)
{
char ch=w[i];
if(temp->children.count(ch))
{
temp=temp->children[ch];
temp->wordcount+=1;
}
else
{
noden=new node(ch);
temp->children[ch]=n;
temp=n;
temp->wordcount+=1;
}
}
temp->terminal=true;
}
void printuniqueprefix(char* w)
{
node*temp=root;
char str[10];
int j=0;
for(int i=0;w[i]!=’\0’;i++)
{
char ch=w[i];
if(temp->children.count(ch))
{
if(temp->wordcount==1)
{
str[j]=’\0’;
cout<<str<<endl;return ;
}
else
{
temp=temp->children[ch];
str[j]=ch;j++;
//cout<<ch<<endl;
//cout<wordcount;
}
}
}
cout<<“NO UNIQUE PREFIX”<<endl;
}
};
int main()
{
trie t;
int n;cin>>n;
char s[n][10];
for(int i=0;i<n;i++)
{
cin>>s[i];
t.insert(s[i]);
}cout<<endl<<endl;
for(int i=0;i<n;i++)
{
t.printuniqueprefix(s[i]);
}
return 0;
}
/*this is the code i wrote for the problem and
if i give input :
4
red
go
goe
fake
output:
r
no unique prefix
no unique prefix
f
but if i give input:
4
red
go
goes
fake
output:
r
no unique prefix
goe
f
*/