题意:
给你多个由0-9构成的字符串集合,问你这个集合中是否有一个字符串是其他字符串的前缀?
分析:
直接构造字典树,然后一一插入每个字符串,判断是否有比当前字符串短或长的同一路径的字符串已经在树中了.
#include<bits/stdc++.h>using namespace std;const int maxn = 100111;struct trie
{int ch[maxn][10];int v[maxn];int sz;void init(){sz=1;v[0]=0;memset(ch[0],0,sizeof ch[0]);}bool insert(char *s){bool ok=true;int n=strlen(s),u=0;for(int i=0;i<n;i++){int id=s[i]-'0';if(ch[u][id]==0){ch[u][id]=sz;v[sz]=0;memset(ch[sz],0,sizeof ch[sz]);sz++;}u=ch[u][id];if(v[u]>0)///路径上有串ok=false;}v[u]=1;z//是尾节点if(ok){for(int i=0;i<10;i++){if(ch[u][i]!=0){ok=false;///自己是别的串的前缀break;}}}return ok;}
}trie;char s[22];int main()
{int t;cin>>t;while(t--){int n;cin>>n;trie.init();bool ok = true;for(int i=0;i<n;i++){scanf("%s",s);if(ok)ok=trie.insert(s);}if(ok)puts("YES");else puts("NO");}
}