Advertisement
Guest User

Untitled

a guest
Jan 8th, 2015
352
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. struct hash_table
  5. {
  6. const int P = 179, Q = 2000000;
  7. string str[2000000];
  8. int nxt[2000000];
  9. long long hash_str(string s)
  10. {
  11. long long ans = 0;
  12. for (int i = 0; i < s.length(); i++)
  13. {
  14. ans = (ans*P + s[i]) % Q;
  15. }
  16. return ans;
  17. }
  18. bool check(string s)
  19. {
  20. long long hash_s = hash_str(s);
  21. int pos = hash_s;
  22. while (nxt[pos]!=pos)
  23. {
  24. if (str[pos] == s) return true;
  25. pos = nxt[pos];
  26. }
  27. return false;
  28. }
  29. void insert(string s)
  30. {
  31. long long hash_s = hash_str(s);
  32. int pos = hash_s;
  33. while (str[pos] != "")
  34. {
  35. if (pos + 1 < Q)
  36. {
  37. pos++;
  38. }
  39. else
  40. {
  41. pos = 0;
  42. }
  43. }
  44. str[pos] = s;
  45. if (pos != hash_s)
  46. {
  47. nxt[hash_s] = pos;
  48. }
  49. }
  50. };
  51. hash_table ht;
  52. int main()
  53. {
  54. ios::sync_with_stdio(false);
  55. cin.tie(0);
  56. while (1)
  57. {
  58. char m;
  59. cin >> m;
  60. if (m == '+')
  61. {
  62. string s;
  63. cin >> s;
  64. ht.insert(s);
  65. }
  66. else if (m == '?')
  67. {
  68. string s;
  69. cin >> s;
  70. if (ht.check(s))
  71. {
  72. cout << "YES\n";
  73. }
  74. else
  75. {
  76. cout << "NO\n";
  77. }
  78. }
  79. else if (m == '#')
  80. {
  81. break;
  82. }
  83. }
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement