这是一道Trie树模板题. Trie树也叫字典树, 采用类似字典一样的索引方法, 把边看做字符, 把多条字符串建立成树, 达到字符串快速检索, 资瓷插入和查找两个操作.
Trie树的思想一句话概括就是相同的前缀共用同一条链, 在不同的地方产生分支, 在字符串的结束位置打标记. 每个节点有size个指针指向后继, size为字符集大小, 空间复杂度最坏为$latex O(N*size)$, N为总字符数.
插入时扫描要插入的串, 每个节点判断一下是否已经存在, 存在就沿着已有的指针走, 否则就新建节点, 建立指针. 扫完字符串在最后一个节点打标记.
查找时存在指针就沿着走, 扫完字符串时看节点有没有标记, 不存在就这个字符串不存在.
本题可以先把所有字符串插入, 再查询每一个串, 如果在查的过程中没有碰到打的结束标记, 就证明当前串是某个其他串的前缀, 输出NO.
#include<cstdio> #include<cstring> #define in inline #define re register in int read() { int s(0),b(0);char ch; do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9'); while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); if(b) return -s; return s; } const int size=100100; int T,n,trie[size][10],end[size],cnt=1; in void insert(char s[]) { int p=1,l=strlen(s); for(re int i=0;i<l;++i) { if(trie[p][s[i]-48]) p=trie[p][s[i]-48]; else trie[p][s[i]-48]=++cnt,p=cnt; } end[p]=1; } in bool chk(char s[]) { int p=1,l=strlen(s),f=1; for(re int i=0;i<l;++i) { if(end[p]) f=0; if(trie[p][s[i]-48]) p=trie[p][s[i]-48]; else break; } return f; } signed main() { T=read(); while(T--) { n=read(); char s[10002][11];bool f=true; for(re int i=1;i<=n;++i){scanf("%s",s[i]);insert(s[i]);} for(re int i=1;i<=n;++i) { f=chk(s[i]); if(!f){printf("NO\n");break;} } if(f) printf("YES\n"); memset(end,0,sizeof(end)); memset(trie,0,sizeof(trie)); cnt=1; } return 0; }
最新评论