Advertisement
Mlxa

ALGO String bor (like multiset)

Jan 30th, 2018
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <cassert>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <vector>
  6. typedef long long ll;
  7.  
  8.  
  9. namespace Mlxa {
  10.     using namespace std;
  11.     typedef   long long         ll;
  12.  
  13.     #define read                cin
  14.     #define eol                 '\n'
  15.     #define endln               cout << eol
  16.     #ifdef AC
  17.         #define clog cerr
  18.     #else
  19.         #define clog 0
  20.     #endif
  21.  
  22.     template <class A>              inline void print   (A a)           { cout << a << ' '; }
  23.     template <class A>              inline void println (A a)           { cout << a << eol; }
  24.     template <class A, class... B>  inline void println (A a, B... b)   { print(a); println(b...); }
  25.  
  26.     template <class A>              inline void err     (A a)         { clog << a << ' '; }
  27.     template <class A>              inline void errln   (A a)         { clog << a << eol; }
  28.     template <class A, class... B>  inline void errln   (A a, B... b) { clog << a << ' '; errln(b...); }
  29.     #define                                     addLog(...) errln("log:", __VA_ARGS__)
  30.  
  31.     template <class A> inline ll getSize(A a) { return a.size(); }
  32.     #define pb                  push_back
  33.     #define mp                  make_pair
  34.     #define all(x)              begin(x), end(x)
  35.  
  36.     #define openFiles(name)     freopen(name ".in", "r", stdin), freopen(name ".out", "w", stdout)
  37.     #define fastIO              ios_base::sync_with_stdio(false), cin.tie(nullptr)
  38. } using namespace Mlxa;
  39.  
  40. namespace bor
  41. {
  42.     const size_t abcSize = 256;
  43.     struct Node
  44.     {
  45.         Node *child[abcSize];
  46.         size_t nTerminal;
  47.         Node () : nTerminal(false)
  48.         {
  49.             for (size_t i = 0; i < abcSize; ++ i)
  50.                 child[i] = nullptr;
  51.         }
  52.     }; typedef Node *Ptr;
  53.  
  54.     void printSorted (Ptr root, string cur)
  55.     {
  56.         if (root)
  57.         {
  58.             for (size_t i = 0; i < root->nTerminal; ++ i)
  59.             println(cur);
  60.  
  61.             for (size_t i = 0; i < abcSize; ++ i)
  62.             if (root->child[i])
  63.                 printSorted(root->child[i], cur + char(i));
  64.         }
  65.     }
  66.  
  67.     void addString (Ptr root, string s)
  68.     {
  69.         Ptr v = root;
  70.         for (size_t i = 0; i < s.size(); ++ i) {
  71.             assert(v);
  72.             size_t c = s[i];
  73.             if (not v->child[c])
  74.                 v->child[c] = new Node;
  75.             v = v->child[c];
  76.         }
  77.         ++ v->nTerminal;
  78.     }
  79.  
  80.     size_t countString (Ptr root, string s)
  81.     {
  82.         Ptr v = root;
  83.         for (size_t i = 0; i < s.size(); ++ i) {
  84.             assert(v);
  85.             size_t c = s[i];
  86.             if (not v->child[c])
  87.                 return 0;
  88.             v = v->child[c];
  89.         }
  90.         return v->nTerminal;
  91.     }
  92.  
  93.     size_t eraseOne (Ptr root, string s)
  94.     {
  95.         Ptr v = root;
  96.         for (size_t i = 0; i < s.size(); ++ i) {
  97.             assert(v);
  98.             size_t c = s[i];
  99.             if (not v->child[c])
  100.                 return 0;
  101.             v = v->child[c];
  102.         }
  103.         -- v->nTerminal;
  104.         return 1;
  105.     }
  106.  
  107.     size_t setNTo (Ptr root, string s, size_t to)
  108.     {
  109.         Ptr v = root;
  110.         for (size_t i = 0; i < s.size(); ++ i) {
  111.             assert(v);
  112.             size_t c = s[i];
  113.             if (not v->child[c])
  114.                 return 0;
  115.             v = v->child[c];
  116.         }
  117.         size_t change = v->nTerminal - to;
  118.         v->nTerminal = to;
  119.         return change;
  120.     }
  121.  
  122.     struct Bor
  123.     {
  124.         Ptr root;
  125.         size_t size;
  126.  
  127.         void insert (string s)
  128.         {   ++ size; addString(root, s); }
  129.  
  130.         size_t count (string s)
  131.         {   return countString(root, s); }
  132.  
  133.         void erase (string s)
  134.         {   size -= eraseOne(root, s);  }
  135.  
  136.         void setCount (string s, size_t to)
  137.         {   size -= setNTo(root, s, to); }
  138.  
  139.         void print ()
  140.         {   printSorted(root, "[CONTAINS]:\t"); }
  141.  
  142.         Bor () : root(new Node), size(0) {}
  143.     };
  144. }
  145.  
  146. using namespace bor;
  147. int main () {
  148.     Bor set;
  149.     println("Best string multiset in the world)))");
  150.  
  151.     string command, arg;
  152.     size_t a;
  153.  
  154.     while (read >> command)
  155.     {
  156.         if (command == "print")
  157.         {
  158.             set.print();
  159.         }
  160.         else if (command == "add")
  161.         {
  162.             read >> arg;
  163.             set.insert(arg);
  164.         }
  165.         else if (command == "erase")
  166.         {
  167.             read >> arg;
  168.             set.erase(arg);
  169.         }
  170.         else if (command == "size")
  171.         {
  172.             println(set.size);
  173.         }
  174.     }
  175.  
  176.     return 0;
  177. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement