裸Trie
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<cstdlib> 7 using namespace std; 8 char st[105]; 9 int ch[100005][105],sum; 10 bool bo[100005]; 11 void init() 12 { 13 memset(ch,0,sizeof(ch)); memset(bo,false,sizeof(bo)); 14 } 15 bool insert(char *s) 16 { 17 int n=strlen(s); bool flag=false; int u=1; 18 for (int i=0; i<n; i++){ 19 int c=s[i]-'0'; 20 if (!ch[u][c]) ch[u][c]=++sum; 21 else if (i==n-1) flag=true; 22 u=ch[u][c]; 23 if (bo[u]) flag=true; 24 } 25 bo[u]=true; return flag; 26 } 27 int main() 28 { 29 int T; 30 scanf("%d",&T); 31 while (T--){ 32 int n; 33 scanf("%d",&n); bool ans=false; 34 init(); 35 sum=1; 36 for (int i=1; i<=n; i++){ 37 scanf("%s",st); 38 if (insert(st)) ans=true; 39 } 40 if (!ans) puts("YES"); else puts("NO"); 41 } 42 return 0; 43 }
miao~~~