Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <cstdio>
- #include <cmath>
- #include <vector>
- typedef long long ll;
- namespace Mlxa {
- using namespace std;
- typedef long long ll;
- #define read cin
- #define eol '\n'
- #define endln cout << eol
- #ifdef AC
- #define clog cerr
- #else
- #define clog 0
- #endif
- template <class A> inline void print (A a) { cout << a << ' '; }
- template <class A> inline void println (A a) { cout << a << eol; }
- template <class A, class... B> inline void println (A a, B... b) { print(a); println(b...); }
- template <class A> inline void err (A a) { clog << a << ' '; }
- template <class A> inline void errln (A a) { clog << a << eol; }
- template <class A, class... B> inline void errln (A a, B... b) { clog << a << ' '; errln(b...); }
- #define addLog(...) errln("log:", __VA_ARGS__)
- template <class A> inline ll getSize(A a) { return a.size(); }
- #define pb push_back
- #define mp make_pair
- #define all(x) begin(x), end(x)
- #define openFiles(name) freopen(name ".in", "r", stdin), freopen(name ".out", "w", stdout)
- #define fastIO ios_base::sync_with_stdio(false), cin.tie(nullptr)
- } using namespace Mlxa;
- namespace bor
- {
- const size_t abcSize = 256;
- struct Node
- {
- Node *child[abcSize];
- size_t nTerminal;
- Node () : nTerminal(false)
- {
- for (size_t i = 0; i < abcSize; ++ i)
- child[i] = nullptr;
- }
- }; typedef Node *Ptr;
- void printSorted (Ptr root, string cur)
- {
- if (root)
- {
- for (size_t i = 0; i < root->nTerminal; ++ i)
- println(cur);
- for (size_t i = 0; i < abcSize; ++ i)
- if (root->child[i])
- printSorted(root->child[i], cur + char(i));
- }
- }
- void addString (Ptr root, string s)
- {
- Ptr v = root;
- for (size_t i = 0; i < s.size(); ++ i) {
- assert(v);
- size_t c = s[i];
- if (not v->child[c])
- v->child[c] = new Node;
- v = v->child[c];
- }
- ++ v->nTerminal;
- }
- size_t countString (Ptr root, string s)
- {
- Ptr v = root;
- for (size_t i = 0; i < s.size(); ++ i) {
- assert(v);
- size_t c = s[i];
- if (not v->child[c])
- return 0;
- v = v->child[c];
- }
- return v->nTerminal;
- }
- size_t eraseOne (Ptr root, string s)
- {
- Ptr v = root;
- for (size_t i = 0; i < s.size(); ++ i) {
- assert(v);
- size_t c = s[i];
- if (not v->child[c])
- return 0;
- v = v->child[c];
- }
- -- v->nTerminal;
- return 1;
- }
- size_t setNTo (Ptr root, string s, size_t to)
- {
- Ptr v = root;
- for (size_t i = 0; i < s.size(); ++ i) {
- assert(v);
- size_t c = s[i];
- if (not v->child[c])
- return 0;
- v = v->child[c];
- }
- size_t change = v->nTerminal - to;
- v->nTerminal = to;
- return change;
- }
- struct Bor
- {
- Ptr root;
- size_t size;
- void insert (string s)
- { ++ size; addString(root, s); }
- size_t count (string s)
- { return countString(root, s); }
- void erase (string s)
- { size -= eraseOne(root, s); }
- void setCount (string s, size_t to)
- { size -= setNTo(root, s, to); }
- void print ()
- { printSorted(root, "[CONTAINS]:\t"); }
- Bor () : root(new Node), size(0) {}
- };
- }
- using namespace bor;
- int main () {
- Bor set;
- println("Best string multiset in the world)))");
- string command, arg;
- size_t a;
- while (read >> command)
- {
- if (command == "print")
- {
- set.print();
- }
- else if (command == "add")
- {
- read >> arg;
- set.insert(arg);
- }
- else if (command == "erase")
- {
- read >> arg;
- set.erase(arg);
- }
- else if (command == "size")
- {
- println(set.size);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement