首页 > 代码库 > hdu杭电1671 / poj3630 字典树

hdu杭电1671 / poj3630 字典树

2024-08-13 07:15:39   218人阅读

传送门

题意：输入n串数字 找出是否有前缀相同的串 如果存在 输出NO否则输出YES

思路：用字典树解决 标记字典树总串的结尾 查找出一个串内部是否有被标记的节点 如果有那么说明存在前缀相同的串

在插入字典树的时候判断是否存在

AC代码：

 

 1 #include "iostream" 2 #include "stdio.h" 3 #include "string.h" 4 using namespace std; 5  6 using namespace std ; 7 typedef long long ll; 8 #define mem(a) memset(a,0,sizeof(a)) 9 10 typedef struct Trie11 {12     bool isword;13     struct Trie *next[10];14 }*Trie_pointer;15 16 Trie trie[300005];17 18 int tot,flag;19 20 Trie_pointer CreateNode()21 {22     return &trie[tot++];23 }24 25 void Insert(Trie_pointer root, char *s)26 {27     if(*s == ‘\0‘)28         return;29     char *p = s;30     Trie_pointer tmp,t = root;31     while(*p != ‘\0‘)32     {33         if(t->next[*p - ‘0‘] == NULL)34         {35             tmp = CreateNode();36             t->next[*p - ‘0‘] = tmp;37         }38         t = t->next[*p - ‘0‘];39         p++;40         if(t->isword == 1)41             flag = 1;42     }43     t->isword = 1;44     for(int i=0; i<10; i++)45     {46         if(t->next[i] != NULL)47             flag = 1;48     }49 }50 51 int main()52 {53     Trie root;54     char s[2005];55     int i,n,t;56     cin>>t;57     while(t--)58     {59         memset(trie,0,sizeof(trie));60         memset(&root,0,sizeof(root));61         tot=0;62         cin>>n;63         while(n--)64         {65             cin>>s;66             if(!flag)67                 Insert(&root,s);68         }69         if(flag)70             printf("NO\n");71         else72             printf("YES\n");73         flag = 0;74     }75     return 0;76 }

 

hdu杭电1671 / poj3630 字典树


联系
我们