题目描述
输入格式
输出格式
样例
样例输入
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(￣▽￣)ブ
