Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string>
- using namespace std;
- struct hash_table
- {
- const int P = 179, Q = 2000000;
- string str[2000000];
- int nxt[2000000];
- long long hash_str(string s)
- {
- long long ans = 0;
- for (int i = 0; i < s.length(); i++)
- {
- ans = (ans*P + s[i]) % Q;
- }
- return ans;
- }
- bool check(string s)
- {
- long long hash_s = hash_str(s);
- int pos = hash_s;
- while (nxt[pos]!=pos)
- {
- if (str[pos] == s) return true;
- pos = nxt[pos];
- }
- return false;
- }
- void insert(string s)
- {
- long long hash_s = hash_str(s);
- int pos = hash_s;
- while (str[pos] != "")
- {
- if (pos + 1 < Q)
- {
- pos++;
- }
- else
- {
- pos = 0;
- }
- }
- str[pos] = s;
- if (pos != hash_s)
- {
- nxt[hash_s] = pos;
- }
- }
- };
- hash_table ht;
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- while (1)
- {
- char m;
- cin >> m;
- if (m == '+')
- {
- string s;
- cin >> s;
- ht.insert(s);
- }
- else if (m == '?')
- {
- string s;
- cin >> s;
- if (ht.check(s))
- {
- cout << "YES\n";
- }
- else
- {
- cout << "NO\n";
- }
- }
- else if (m == '#')
- {
- break;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement