题意:给你n个字符串,如果有字符串是另一个字符串的前缀,则输出NO,否则YES。
思路:本来就是为了学习trie树才做这题的,自然是trie来解决。有一定数据结构基础的应该很好懂。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; struct node { int d[11]; int cnt; }t[111111]; int n,num; void build(char *a) { int p=0; int l=strlen(a); for(int i=0;i<l;i++) { if(t[p].d[a[i]-'0']==0) { t[p].d[a[i]-'0']=++num; memset(t[num].d,0,sizeof(t[num].d)); t[num].cnt=0; } p=t[p].d[a[i]-'0']; t[p].cnt++; } } int search(char *a) { int p=0; int l=strlen(a); for(int i=0;i<l;i++) { p=t[p].d[a[i]-'0']; } return t[p].cnt; } char a[111111][111]; int main() { int ttt; scanf("%d",&ttt); while(ttt--) { num=0; memset(t[0].d,0,sizeof(t[0].d)); t[0].cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",&a[i]); build(a[i]); } int flag=0; for(int i=1;i<=n;i++) { if(search(a[i])>1) { flag=1; break; } } if(flag)cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }