jakaria_hossain

UVA - Phone List (trie tree)

May 8th, 2019
102
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int flag;
  4. int last,cur, len,id;
  5. string str;
  6. struct node
  7. {
  8. bool endmark;
  9. int next[13];
  10.  
  11. } root[100000];
  12. void trie(int cur)
  13. {
  14. for (int i = 0; i < 10; i++)
  15. root[cur].next[i] = -1;
  16.  
  17. root[cur].endmark=false;
  18. }
  19. void insert()
  20. {
  21. cur=0;
  22. len=str.size();
  23. for (int i = 0; i < len; i++)
  24. {
  25. id = str[i] - 48;
  26. if (root[cur].next[id]==-1)
  27. {
  28. root[cur].next[id]=last;
  29. trie(last++);
  30. cur = root[cur].next[id];
  31. }
  32. else
  33. {
  34. cur = root[cur].next[id];
  35. if(root[cur].endmark==true)
  36. {
  37. flag=1;
  38. }
  39. if(i==len-1)
  40. flag = 1;
  41. }
  42. if(flag==1)
  43. break;
  44. }
  45. root[cur].endmark = true;
  46. }
  47.  
  48.  
  49. int main()
  50. {
  51.  
  52. int test;
  53. cin>>test;
  54. while(test--)
  55. {
  56. flag=0;
  57. last=1;
  58. trie(0);
  59. int n;
  60. cin>>n;
  61. for(int i=0; i<n; i++)
  62. {
  63. cin>>str;
  64. insert();
  65. }
  66. if(flag==1)
  67. cout<<"NO"<<endl;
  68. else
  69. cout<<"YES"<<endl;
  70. }
  71. return 0;
  72. }
RAW Paste Data