和前缀统计这道题很像,可以配合食用,对于每次读入的数据我们将其insert的同时判断一下1:是否有创建新的节点。2:是否存在字符串结尾的标志。
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+10,INF=1e8;
int idx,son[N][15],n,t;
char str[15];
bool vis[N];
int insert(char str[])
{
int p=0;
bool ok=true;
bool first=false;
for(int i=0;str[i];i++)
{
int u=str[i]-'0';
if(!son[p][u])
{
son[p][u]=++idx;
first=true;
}
p=son[p][u];
if(vis[p]) ok=false;
}
vis[p]=true;
return ok&&first;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while(t--)
{
int f=0;
cin>>n;
while(n--)
{
cin>>str;
if(!insert(str)) f=1;
}
if(f) puts("NO");
else puts("YES");
memset(vis,0,sizeof vis);
memset(son,0,sizeof son);
idx=0;
}
return 0;
}