题意:输入n串数字 找出是否有存在串的前缀与另一个串相同 如果存在 输出NO否则输出YES
思路:用字典树解决 标记字典树总串的结尾 查找出一个串内部是否有被标记的节点 如果有那么说明存在前缀相同的串
在插入字典树的时候判断是否存在 cin poj tle了 还是换成gets才过。。。
AC代码:
#include "iostream"
#include "stdio.h"
#include "string.h"
using namespace std; using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a)) typedef struct Trie
{
bool isword;
struct Trie *next[];
}*Trie_pointer; Trie trie[]; int tot,flag; void Insert(Trie_pointer root, char *s)
{
if(*s == '\0')
return;
char *p = s;
Trie_pointer tmp,t = root;
while(*p != '\0')
{
if(t->next[*p - ''] == NULL)
{
tmp = &trie[tot++];
t->next[*p - ''] = tmp;
}
t = t->next[*p - ''];
p++;
if(t->isword == )
flag = ;
}
t->isword = ;
for(int i=; i<; i++)
{
if(t->next[i] != NULL)
flag = ;
}
} int main()
{
Trie root;
char s[];
int i,n,t;
cin>>t;
while(t--)
{
memset(trie,,sizeof(trie));
memset(&root,,sizeof(root));
tot=;
cin>>n;
getchar();
while(n--)
{
gets(s);
if(!flag)
Insert(&root,s);
}
if(flag)
printf("NO\n");
else
printf("YES\n");
flag = ;
}
return ;
}