题目描述
输入格式
输出格式
样例
样例输入
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
样例输出
NO
YES
数据范围与提示
这道题的三条判断是否存在前缀的标准：
-
当在建树字符串已经到结尾时，如果该点有结束标记，那肯定是前缀（
不是真前缀） -
当在建树字符串已经到结尾时，如果该点还有子节点，那也是前缀
-
当在建树过程中经过了某个结束标记，表明存在前缀（此时之前的某个字符串是当前插入的字符串的前缀）
-
我觉得这道题最巧妙的地方就是不是在search里面判断而是变插变在insert里面判断
-
在插入时一定要从0开始遍历，不然就会像我一样一直WA
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int t,n,trie[maxn*12][12],tot;
bool ed[maxn*12];
string a;
bool insert(const string &b)
{
int len=b.length(),p=1;bool flag=0;
for (int i=0;i<len;i++)
{
int ch=b[i]-'0';
if (!trie[p][ch]) trie[p][ch]=++tot;
else if (i==len-1) //结尾已经有点
flag=1;
p=trie[p][ch];
if (ed[p])//经过了结束标记
flag=1;
}
ed[p]=1;
return flag;
}
int main()
{
scanf("%d",&t);
while (t--)
{
tot=1;bool x=0;
scanf("%d",&n);
memset(trie,0,sizeof(trie));
memset(ed,0,sizeof(ed));
for (int i=1;i<=n;i++)
{
cin>>a;
if (insert(a)) x=1;
}
if (x) printf("NO\n");
else printf("YES\n");
}
return 0;
}
完结撒花！o(￣▽￣)ブ
标签：insert,12,前缀,int,样例,List,Phone,maxn From： https://www.cnblogs.com/zhagnxinyue/p/18173508