Description
给定\(n\)个长度不超过\(10\)的数字串，判断是否有两个字符串\(A\)和\(B\),满足\(A\)是\(B\)的前缀，若有，输出
NO，若没有，输出YES。
一道\(Trie\)树裸题,我交了20次.
呜呜呜呜,难受.
刚开始是看错题,有的话输出"NO"，没有输出“YES”什么鬼题啊!!!
一眼看到就会切了的.害得我交了20次啊!
定义数组：
\(ok[v]\)表示以\(v\)为结尾的字符串是否出现过.
\(cnt[u]\)代表当前节点被遍历过几次,判断插入的某字符串的末尾是否被经历过两次以上.
输出即可.
记得\(memset\).
代码
#include<cstdio>
#include<cstring>
#define clear(a) memset(a,0,sizeof a)
#define R register
using namespace std;
int tri[100005][12],n,T,rt,tot,cnt[100005];
char s[15];
bool flg,ok[100005];
inline void insert(int u,char *s)
{
int len=strlen(s);
for(R int i=0;i<len;i++)
{
int v=s[i]-'0';
if(!tri[u][v])
tri[u][v]=++tot;
u=tri[u][v];
cnt[u]++;
if(ok[u])flg=true;
}
ok[u]=true;
if(cnt[u]>1)flg=true;
}
int main()
{
scanf("%d",&T);
while(T--)
{
flg=false;
clear(tri);clear(ok);
clear(cnt);tot=0;
scanf("%d",&n);
for(R int i=1;i<=n;i++)
{
scanf("%s",s);
insert(rt,s);
}
puts(flg?"NO":"YES");
}
}