众所周知这几乎是Trie的模板题,但我在普通做法的基础上大大优化时间和空间。
假设有一个串是某个串的前缀,则存在$i<j,s_i是s_j的前缀或s_j是s_i的前缀$(听起来很弱智?继续往下看)
利用好这个性质能大幅优化空间:
假设当前的串是$s_i$,且$s_j(1\le j<i)$已经存入Trie,那么我们只需要处理上面提及的两种情况,而不需要保存每个串:
1. Trie中某个串是$s_i$的前缀:从根开始沿$s_i$往下走,如果路径上有某个点是叶子节点,则Trie中某个串是$s_i$的前缀。
2. $s_i$是Trie中某个串的前缀:走到$s_i$的叶子节点后,如果这个节点有孩子,那么$s_i$就是某个串的前缀
先查再插入即可。
优化时间:对于每组数据都对Trie进行memset太过浪费了,在开新点时清空它的叶子标记和孩子即可。
时间复杂度有点玄学,就不分析了。
(另外,写这篇题解的时候想到了一个更秒的做法:先把所有串都插入Trie,然后从Trie的根开始dfs,如果如何一条路径上遇到多于一个的叶子标记就是NO,反之YES)
//Wan Hong 2.2
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 100011
struct Trie
{
int t[MAXN][11],cnt;
bool leaf[MAXN];
void build()//用了一点小技巧,在开新点时清空它的信息,避免memset多次
{
cnt=1;
for(ll i=0;i<=9;++i)t[1][i]=0;
}
void insert(char* a)
{
ll n=strlen(a),u=1;
for(ll i=0;i<n;++i)
{
int &v=t[u][a[i]-'0'];
if(!v)
{
v=++cnt;
leaf[v]=0;
for(ll i=0;i<=9;++i)t[v][i]=0;
}
u=v;
}
leaf[u]=1;
}
bool query(char* a)
{
ll n=strlen(a),u=1;
for(ll i=0;i<n;++i)
{
int &v=t[u][a[i]-'0'];
if(leaf[v])return 1;
if(!v)return 0;
u=v;
}
for(ll i=0;i<=9;++i)
if(t[u][i])return 1;
return 0;
}
}t;
char a[MAXN];
int main()
{
ll T=read();
while(T--)
{
t.build();
ll n=read();
bool flag=0;
for(ll i=1;i<=n;++i)
{
scanf("%s",a);
if(!flag)
{
flag|=t.query(a);
t.insert(a);
}
}
if(flag)puts("NO");
else puts("YES");
}
return 0;
}