一道字典树的模板题，每次插入前查询是否有该串的某个前缀子串存在，或者该串是否某个串的前缀。具体实现是在插入时串的结尾做一个标记，如果某一个串在查询的时候找到一个标记，说明存在前缀；第二种情况是这个串遍历结束后还是没有发现一个空的，也即该串是某个串的子串。最后需要注意的是动态申请空间需要及时释放空间，不然会MLE。
AC代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node
{
node *ne[];
int v;
}*head;
void insert(char *s)
{
node *p=head,*q;
for(int i=;s[i];i++)
{
int id=s[i]-'';
if(p->ne[id]==NULL)
{
q=(node*)malloc(sizeof(node));
for(int j=;j<;j++)
q->ne[j]=NULL;
q->v=;
p->ne[id]=q;
p=p->ne[id];
}
else
{
p=p->ne[id];
}
}
p->v=-;
}
int Q(char *s)
{
node *p=head;
for(int i=;s[i];i++)
{
int id=s[i]-'';
p=p->ne[id];
if(p==NULL)
return ;
if(p->v==-)
return -;
}
return -;
}
void clean(node *p)
{
if(p==NULL) return ;
for(int i=;i<;i++)
{
if(p->ne[i]!=NULL)
clean(p->ne[i]);
}
free(p);
return ;
}
int main()
{
int t,n;
char s[];
scanf("%d",&t);
while(t--)
{
head=(node*)malloc(sizeof(node));
for(int i=;i<;i++)
head->ne[i]=NULL;
scanf("%d",&n);
int f=;
while(n--)
{
scanf("%s",s);
if(Q(s)==-){
f=;
//printf("%s+++\n",s);
}
if(f) continue;
insert(s);
}
if(f) puts("NO");
else puts("YES");
clean(head);
}
return ;
}