本文共 1497 字，大约阅读时间需要 4 分钟。
参考http://s.acmore.net/show_article/show/58
以附上代码
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std;12 #define Max(a,b) (a > b ? a : b)13 #define Min(a,b) (a < b ? a : b)14 15 int Trie[500000][10];16 int val[100000];17 int S = 1;18 int idx(char c) { return c - '0';}19 20 void init()21 {22 S = 1;23 memset(Trie,0,sizeof(Trie));24 memset(val,-1,sizeof(val));25 }26 27 int search_insert(char* s)28 {29 int u = 0;30 int n = strlen(s);31 for(int i = 0; i < n; i++)32 {33 int c = idx(s[i]);34 if(!Trie[u][c])35 { //这个结点不存在，插入36 Trie[u][c] = S;37 val[u] = 0;//标记这个结点是单词结点38 u = S;39 S++;//结点加140 }41 else if(Trie[u][c] && val[u] == 0)42 { //如果这个结点存在，而且是单词结点，那么就往下走43 u = Trie[u][c];44 if(val[u] == 1)45 { //当下一个结点是单词的结束时，直接返回false，表示存在前缀。46 return 0;47 }48 }49 else if(val[u] == 1)50 {51 return 0;52 }53 }54 if(val[u] == 1 || val[u] == 0)55 { //检测是不是有前缀56 return 0;57 }58 else59 { //设置新单词的结尾标记60 val[u] = 1;61 }62 return 1;63 }64 65 int main()66 {67 //freopen("in.txt","r",stdin);68 int t,n;69 char a[100000];70 scanf("%d",&t);71 while(t--)72 {73 int flag = 1;74 init();75 scanf("%d",&n);76 while(n--)77 {78 scanf("%s",a);79 if(!search_insert(a))80 {81 flag = 0;82 }83 }84 if(flag)85 {86 printf("YES\n");87 }88 else89 {90 printf("NO\n");91 }92 }93 return 0;94 }
转载于:https://www.cnblogs.com/gj-Acit/p/3145042.html