Advertisement
Guest User

Untitled

a guest
May 1st, 2016
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3.  
  4.  
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9. int ch[10];
  10. bool isword;
  11. };
  12.  
  13. long long ar[10005];
  14.  
  15. int nodecount;
  16.  
  17. struct node trie[20000];
  18.  
  19. void init()
  20. {
  21. nodecount=1;
  22. }
  23.  
  24. string stringki(long long a)
  25. {
  26. string ans;
  27. stringstream ss;
  28. ss << a;
  29. ans=ss.str();
  30. return ans;
  31. }
  32.  
  33.  
  34. int t,n;
  35. bool ans;
  36.  
  37. string temp;
  38.  
  39. bool trie_insert(string s)
  40. {
  41. int next,cur=1;
  42. for(int i=0;i<s.size();i++)
  43. {
  44. int letter=s[i]-'0';
  45. next=trie[cur].ch[letter];
  46. if(next==0)
  47. {
  48. nodecount++;
  49. trie[cur].ch[letter]=nodecount;
  50. cur=nodecount;
  51. }
  52. else
  53. {
  54. cur=next;
  55. }
  56. if(trie[cur].isword)
  57. {
  58. return true;
  59. }
  60. }
  61. trie[cur].isword=true;
  62. return false;
  63. }
  64.  
  65.  
  66. int main()
  67. {
  68. cin>>t;
  69. for(int kz=0;kz<t;kz++)
  70. {
  71. init();
  72. cin>>n;
  73. for(int i=0;i<n;i++)
  74. {
  75. cin>>ar[i];
  76. }
  77. sort(ar,ar+n);
  78. for(int i=0;i<n;i++)
  79. {
  80. temp=stringki(ar[i]);
  81. cout<<temp<<endl;
  82. ans=trie_insert(temp);
  83. cout<<ans<<endl;
  84. if(ans)
  85. {
  86. cout<<"NO\n";
  87. break;
  88. }
  89. if(i==n-1)
  90. {
  91. cout<<"YES\n";
  92. break;
  93. }
  94. }
  95. }
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement