fork download

//Credit: anton_lunyov
 
// Supports the following types of queries on the string S:
// - match(q) - returns the number of occurrences of the string `q` in S,
//              complexity is O(|q| * log |S|).
// - pop()    - deletes the first character of S and returns its value,
//              complexity is O(log |S|).
// - push(c)  - inserts character `c` at the beginning of the string,
//              complexity is O(log^2 |S|).
// - size()   - returns the length of the string,
//              complexity is O(1).
// - at(i)    - returns the i-th character of S in 0-based numeration,
//              complexity is O(1).
// - revat(i) - returns the i-th character of S reversed (in 0-based numeration),
//              it will be convenient for the main class StringDeque,
//              complexity is O(1).
// Occupies O(|S|) memory at each moment.
class DynamicSuffixArray {
 private:
  // The data structure for node of the treap.
  struct Node {
    int left, right, parent;
    int size;  // The size of the subtree.
    int y;     // The key for heap ordering.
 
    // Creates node having all zero links, but with size 1.
    // We will call such node as default node.
    // rand() for y keeps the tree self-balancing.
    Node(): y(rand()), left(0), right(0), parent(0), size(1) {};
  };
 
  // Node nodes_[id] corresponds to the suffix that starts at str_[id].
  vector<char> str_;    // The actual string in reversed order.
  vector<Node> nodes_;  // The nodes of the treap.
  int root_;            // nodes_[root_] is the root of the treap.
 
 public:
  // Creates dummy zero character and zero node, and sets root to 0.
  DynamicSuffixArray() {
    str_.push_back(0);
    nodes_.push_back(Node());
    nodes_[0].size = 0;  // The size is 1 by default so we fix this.
    root_ = 0;           // Indicates that the tree is empty.
  }
  // To construct dynamic suffix array by string we should push all characters
  // of the string in reversed order. So complexity is O(|S| * log^2 |S|).
  // TODO: Implement a constructor by string using usual suffix array
  // with complexity O(|S| * log |S|) or even O(|S|).
 
  // Returns the number of occurrences of the string `q` in the string S.
  int match(const string& q) {
    return match(root_, q, false, false);
  }
 
  // Deletes the first character of the string and returns its value.
  char pop() {
    remove(size());  // Removes last node from the tree and updates the root.
    nodes_.pop_back();
    char c = str_.back();
    str_.pop_back();
    return c;
  }
 
  // Inserts character `c` to the beginning of the string.
  void push(char c) {
    str_.push_back(c);         // We add `c` to the array `str_`.
    nodes_.push_back(Node());  // We add default node to the array `nodes_`...
    // ...and then actually insert this node to the tree and update the root.
    // We pass the order statistic of (id-1)-th suffix to speed up the solution.
    int id = size();
    root_ = insert(root_, id, getIndex(id - 1));
  }
 
  // Returns the length of the string.
  int size() {
    return str_.size() - 1;  // "-1" because of the dummy zero character.
  }
 
  // Returns the i-th character of the string in 0-based numeration.
  char at(int i) {
    // Recall that the 0-th character of S is `size()`-th character in `str_`.
    return str_[size() - i];
  }
 
  // Returns the i-th character of the reversed string in 0-based numeration.
  char revat(int i) {
    return str_[i + 1];  // "+1" because of the dummy zero character.
  }
 
 private:
  // See editorial for details.
  int match(int tree, const string& q, bool matchLeft, bool matchRight) {
    // For empty subtree the answer is 0.
    if (!tree) {
      return 0;
    }
    // In this case all suffixes in subtree start with `q`.
    if (matchLeft && matchRight) {
      // So the answer is the size of this subtree.
      return nodes_[tree].size;
    }
    for (int i = 0; i < q.size(); ++i) {
      if (q[i] > str_[tree - i]) {
        // Here `matchLeft` should be set to false.
        return match(nodes_[tree].right, q, false, matchRight);
      } else if (q[i] < str_[tree - i]) {
        // While here `matchRight` should be set to false.
        return match(nodes_[tree].left, q, matchLeft, false);
      }
    }
    return 1 +
      match(nodes_[tree].left, q, matchLeft, true) +
      match(nodes_[tree].right, q, true, matchRight);
  }
 
  // Sets parent of node `id` to `parent_id` if `id` is non-zero.
  void setParent(int id, int parent_id) {
    if (id) {
      nodes_[id].parent = parent_id;
    }
  }
 
  // Sets field `size` of the node `id` to the actual size of its subtree.
  // Modifies only non-zero nodes.
  void fixSize(int id) {
    if (id) {
      nodes_[id].size = 1 + 
        nodes_[nodes_[id].left].size +
        nodes_[nodes_[id].right].size;
    }
  }
 
  // Removes node `id` from the tree and update the root.
  // Vector `nodes_` does not change.
  void remove(int id) {
    int par = nodes_[id].parent;
    int tmp = merge(nodes_[id].left, nodes_[id].right);
    // `tmp` is id of node that contains merge of children of the node `id`.
    // `par` is the parent of `tmp` since `tmp` is replacement of `id`.
    setParent(tmp, par);
    if (par) {
      // If `id` has parent then root remains the same,
      // but we need to replace `id` by `tmp` in sons of the node `par`.
      if(nodes_[par].left == id) {
        nodes_[par].left = tmp;
      } else {
        nodes_[par].right = tmp;
      }
      while (par) {
        // Since we delete one node in subtree of `id`,
        // we should decrease the field `size` of each its ancestor by 1.
        nodes_[par].size--;
        par = nodes_[par].parent;
      }
    } else {
      // Otherwise `id` was the root and the new root is `tmp`.
      root_ = tmp;
    }
  }
 
  // Merges subtrees rooted at `L` and `R` and save result in one of the them.
  // Each node in the subtree rooted at `L` should be less than
  // each node in the subtree rooted at `R`.
  int merge(int L, int R) {
    // We return L when R is 0 and R when L is 0.
    if (!L || !R) {
      return L + R;
    }
    // We should preserve the heap property by field `y`.
    if (nodes_[L].y < nodes_[R].y) {
      // In this case `R` should be a root and we merge `L` and left son of `R`,
      // and result is saved in `tmp`.
      int tmp = merge(L, nodes_[R].left);
      // `tmp` will be the new left son of `R`.
      setParent(tmp, R);
      nodes_[R].left = tmp;
      fixSize(R);
      return R;
    } else {
      // In this case `L` will be a root.
      int tmp = merge(nodes_[L].right, R);
      setParent(tmp, L);
      nodes_[L].right = tmp;
      fixSize(L);
      return L;
    }
  }
 
  // Returns the index of `id`-th suffix (the suffix starting at position `id`)
  // in the sorted array of all suffixes (empty suffix has index 0),
  // the so-called order statistic of the suffix.
  int getIndex(int id) {
    // Zero node corresponds to empty suffix and has zero index.
    if (!id) {
      return 0;
    }
    // We add one more the size of its left subtree to the answer.
    int index = nodes_[nodes_[id].left].size + 1;
    while (nodes_[id].parent) {
      int par = nodes_[id].parent;  // Ancestor of the initial node `id`
      if (id == nodes_[par].right) {
        // If node `id` is the right son of `par`,
        // we add one more the size of left subtree of `par` to the answer as above.
        index += nodes_[nodes_[par].left].size + 1;
      }
      id = par;
    }
    return index;
  }
 
  // Returns result of comparison of id1-th and id2-th suffixes.
  // Result is negative if id1-th suffix smaller, positive if it's larger,
  // and zero when they are equal (i.e. when id1 = id2).
  // It is not assumed these suffixes has correct positions in the tree,
  // but (id1-1)-th and (id2-1)-th suffixes should have ones.
  // `index1` is the order statistic of (id1-1)-th suffix.
  int compare(int id1, int id2, int index1) {
    // At first we compare their first characters.
    int cmp = str_[id1] - str_[id2];
    if (cmp == 0)
      // If they are different we compare order statistics
      // for (i-1)-th and (j-1)-th suffixes.
      cmp = index1 - getIndex(id2 - 1);
    return cmp;
  }
 
  // Inserts node `id` to the subtree rooted at `tree`
  // and returns the new root of this subtree (it may change).
  // `index1` is the order statistic of (id-1)-th suffix.
  int insert(int tree, int id, int index1) {
    // In the case of empty subtree the node `id` will be a new root.
    if (!tree) {
      return id;
    }
    // The treap should be a heap by `y` fields.
    // Hence if `id` has larger `y` than `tree`, `id` should be a new root.
    if (nodes_[tree].y < nodes_[id].y) {
      // In this case we split subtree rooted at `tree` into two parts:
      // 1) with suffixes < the `id`-th suffix (the root is left son of `id`);
      // 2) with suffixes > the `id`-th suffix (the root is right son of `id`).
      split(tree, id, index1, nodes_[id].left, nodes_[id].right);
      // We set parents of both left and right sons if `id` to be `id`.
      setParent(nodes_[id].left, id);
      setParent(nodes_[id].right, id);
      fixSize(id);
      return id;  // This case is terminal for insert query.
    }
    // Otherwise we should move `id` to one of the subtrees of the node `tree`,
    // selecting the correct subtree by comparing suffixes at `tree` and `id`.
    int cmp = compare(id, tree, index1);
    if (cmp < 0) {
      // If `id` is less than `tree` than we insert it to the left subtree.
      // `tmp` is the root of this subtree after inserting.
      int tmp = insert(nodes_[tree].left, id, index1);
      // And since root of this subtree could change,
      // we fix relation between `tree` and `tmp`
      setParent(tmp, tree);
      nodes_[tree].left = tmp;
    } else {
      // Now cmp > 0 since all suffixes are different
      // and we insert `id` to the right subtree.
      int tmp = insert(nodes_[tree].right, id, index1);
      setParent(tmp, tree);
      nodes_[tree].right = tmp;
    }
    // We should fix the field `size` of the node `tree`.
    // We can simply increase it by 1 since we add only one node to its subtree.
    nodes_[tree].size++;    
    return tree;  // `tree` remains the root of its subtree
  }
 
  // Splits the subtree rooted at `tree` by the node `id` into two parts:
  // 1) with suffixes < the `id`-th suffix (the root is `L`);
  // 2) with suffixes > the `id`-th suffix (the root is `R`).
  // `id`-th node does not have to be a correct node of the tree.
  // But node `id - 1` should be.
  // `index1` is the order statistic of (id-1)-th suffix.
  void split(int tree, int id, int index1, int& L, int& R) {
    // In the case of empty subtree there is nothing to split,
    // and both `L` and `R` should be empty trees as well.
    if (!tree) {
      L = R = 0;
      return;
    }
    // Otherwise we compare the root of the subtree with the node `id`.
    int cmp = compare(id, tree, index1);
    if (cmp < 0) {
      // If `id` < `tree` then we should split left subtree of `tree` by `id`
      // and place the second subtree to the root of left subtree itself,
      split(nodes_[tree].left, id, index1, L, nodes_[tree].left);
      setParent(nodes_[tree].left, tree);
      R = tree;
    } else {
      // Otherwise cmp > 0 and we split right subtree by the node `id`.
      split(nodes_[tree].right, id, index1, nodes_[tree].right, R);
      setParent(nodes_[tree].right, tree);
      L = tree;
    }
    fixSize(tree);
  }
};
 
 

prog.cpp:33:3: error: ‘vector’ does not name a type
   vector<char> str_;    // The actual string in reversed order.
   ^~~~~~
prog.cpp:34:3: error: ‘vector’ does not name a type
   vector<Node> nodes_;  // The nodes of the treap.
   ^~~~~~
prog.cpp:51:19: error: ‘string’ does not name a type; did you mean ‘struct’?
   int match(const string& q) {
                   ^~~~~~
                   struct
prog.cpp:92:29: error: ‘string’ does not name a type; did you mean ‘struct’?
   int match(int tree, const string& q, bool matchLeft, bool matchRight) {
                             ^~~~~~
                             struct
prog.cpp: In constructor ‘DynamicSuffixArray::Node::Node()’:
prog.cpp:29:15: error: ‘rand’ was not declared in this scope
     Node(): y(rand()), left(0), right(0), parent(0), size(1) {};
               ^~~~
prog.cpp: In constructor ‘DynamicSuffixArray::DynamicSuffixArray()’:
prog.cpp:40:5: error: ‘str_’ was not declared in this scope
     str_.push_back(0);
     ^~~~
prog.cpp:40:5: note: suggested alternative: ‘std’
     str_.push_back(0);
     ^~~~
     std
prog.cpp:41:5: error: ‘nodes_’ was not declared in this scope
     nodes_.push_back(Node());
     ^~~~~~
prog.cpp:41:5: note: suggested alternative: ‘Node’
     nodes_.push_back(Node());
     ^~~~~~
     Node
prog.cpp: In member function ‘char DynamicSuffixArray::pop()’:
prog.cpp:58:5: error: ‘nodes_’ was not declared in this scope
     nodes_.pop_back();
     ^~~~~~
prog.cpp:58:5: note: suggested alternative: ‘Node’
     nodes_.pop_back();
     ^~~~~~
     Node
prog.cpp:59:14: error: ‘str_’ was not declared in this scope
     char c = str_.back();
              ^~~~
prog.cpp:59:14: note: suggested alternative: ‘std’
     char c = str_.back();
              ^~~~
              std
prog.cpp: In member function ‘void DynamicSuffixArray::push(char)’:
prog.cpp:66:5: error: ‘str_’ was not declared in this scope
     str_.push_back(c);         // We add `c` to the array `str_`.
     ^~~~
prog.cpp:66:5: note: suggested alternative: ‘std’
     str_.push_back(c);         // We add `c` to the array `str_`.
     ^~~~
     std
prog.cpp:67:5: error: ‘nodes_’ was not declared in this scope
     nodes_.push_back(Node());  // We add default node to the array `nodes_`...
     ^~~~~~
prog.cpp:67:5: note: suggested alternative: ‘Node’
     nodes_.push_back(Node());  // We add default node to the array `nodes_`...
     ^~~~~~
     Node
prog.cpp: In member function ‘int DynamicSuffixArray::size()’:
prog.cpp:76:12: error: ‘str_’ was not declared in this scope
     return str_.size() - 1;  // "-1" because of the dummy zero character.
            ^~~~
prog.cpp:76:12: note: suggested alternative: ‘std’
     return str_.size() - 1;  // "-1" because of the dummy zero character.
            ^~~~
            std
prog.cpp: In member function ‘char DynamicSuffixArray::at(int)’:
prog.cpp:82:12: error: ‘str_’ was not declared in this scope
     return str_[size() - i];
            ^~~~
prog.cpp:82:12: note: suggested alternative: ‘std’
     return str_[size() - i];
            ^~~~
            std
prog.cpp: In member function ‘char DynamicSuffixArray::revat(int)’:
prog.cpp:87:12: error: ‘str_’ was not declared in this scope
     return str_[i + 1];  // "+1" because of the dummy zero character.
            ^~~~
prog.cpp:87:12: note: suggested alternative: ‘std’
     return str_[i + 1];  // "+1" because of the dummy zero character.
            ^~~~
            std
prog.cpp: In member function ‘int DynamicSuffixArray::match(int, const int&, bool, bool)’:
prog.cpp:100:14: error: ‘nodes_’ was not declared in this scope
       return nodes_[tree].size;
              ^~~~~~
prog.cpp:100:14: note: suggested alternative: ‘Node’
       return nodes_[tree].size;
              ^~~~~~
              Node
prog.cpp:102:27: error: request for member ‘size’ in ‘q’, which is of non-class type ‘const int’
     for (int i = 0; i < q.size(); ++i) {
                           ^~~~
prog.cpp:103:14: error: invalid types ‘const int[int]’ for array subscript
       if (q[i] > str_[tree - i]) {
              ^
prog.cpp:103:18: error: ‘str_’ was not declared in this scope
       if (q[i] > str_[tree - i]) {
                  ^~~~
prog.cpp:103:18: note: suggested alternative: ‘std’
       if (q[i] > str_[tree - i]) {
                  ^~~~
                  std
prog.cpp:105:22: error: ‘nodes_’ was not declared in this scope
         return match(nodes_[tree].right, q, false, matchRight);
                      ^~~~~~
prog.cpp:105:22: note: suggested alternative: ‘Node’
         return match(nodes_[tree].right, q, false, matchRight);
                      ^~~~~~
                      Node
prog.cpp:106:21: error: invalid types ‘const int[int]’ for array subscript
       } else if (q[i] < str_[tree - i]) {
                     ^
prog.cpp:108:22: error: ‘nodes_’ was not declared in this scope
         return match(nodes_[tree].left, q, matchLeft, false);
                      ^~~~~~
prog.cpp:108:22: note: suggested alternative: ‘Node’
         return match(nodes_[tree].left, q, matchLeft, false);
                      ^~~~~~
                      Node
prog.cpp:112:13: error: ‘nodes_’ was not declared in this scope
       match(nodes_[tree].left, q, matchLeft, true) +
             ^~~~~~
prog.cpp:112:13: note: suggested alternative: ‘Node’
       match(nodes_[tree].left, q, matchLeft, true) +
             ^~~~~~
             Node
prog.cpp: In member function ‘void DynamicSuffixArray::setParent(int, int)’:
prog.cpp:119:7: error: ‘nodes_’ was not declared in this scope
       nodes_[id].parent = parent_id;
       ^~~~~~
prog.cpp:119:7: note: suggested alternative: ‘Node’
       nodes_[id].parent = parent_id;
       ^~~~~~
       Node
prog.cpp: In member function ‘void DynamicSuffixArray::fixSize(int)’:
prog.cpp:127:7: error: ‘nodes_’ was not declared in this scope
       nodes_[id].size = 1 +
       ^~~~~~
prog.cpp:127:7: note: suggested alternative: ‘Node’
       nodes_[id].size = 1 +
       ^~~~~~
       Node
prog.cpp: In member function ‘void DynamicSuffixArray::remove(int)’:
prog.cpp:136:15: error: ‘nodes_’ was not declared in this scope
     int par = nodes_[id].parent;
               ^~~~~~
prog.cpp:136:15: note: suggested alternative: ‘Node’
     int par = nodes_[id].parent;
               ^~~~~~
               Node
prog.cpp: In member function ‘int DynamicSuffixArray::merge(int, int)’:
prog.cpp:170:9: error: ‘nodes_’ was not declared in this scope
     if (nodes_[L].y < nodes_[R].y) {
         ^~~~~~
prog.cpp:170:9: note: suggested alternative: ‘Node’
     if (nodes_[L].y < nodes_[R].y) {
         ^~~~~~
         Node
prog.cpp: In member function ‘int DynamicSuffixArray::getIndex(int)’:
prog.cpp:198:17: error: ‘nodes_’ was not declared in this scope
     int index = nodes_[nodes_[id].left].size + 1;
                 ^~~~~~
prog.cpp:198:17: note: suggested alternative: ‘Node’
     int index = nodes_[nodes_[id].left].size + 1;
                 ^~~~~~
                 Node
prog.cpp: In member function ‘int DynamicSuffixArray::compare(int, int, int)’:
prog.cpp:219:15: error: ‘str_’ was not declared in this scope
     int cmp = str_[id1] - str_[id2];
               ^~~~
prog.cpp:219:15: note: suggested alternative: ‘std’
     int cmp = str_[id1] - str_[id2];
               ^~~~
               std
prog.cpp: In member function ‘int DynamicSuffixArray::insert(int, int, int)’:
prog.cpp:237:9: error: ‘nodes_’ was not declared in this scope
     if (nodes_[tree].y < nodes_[id].y) {
         ^~~~~~
prog.cpp:237:9: note: suggested alternative: ‘Node’
     if (nodes_[tree].y < nodes_[id].y) {
         ^~~~~~
         Node
prog.cpp:254:24: error: ‘nodes_’ was not declared in this scope
       int tmp = insert(nodes_[tree].left, id, index1);
                        ^~~~~~
prog.cpp:254:24: note: suggested alternative: ‘Node’
       int tmp = insert(nodes_[tree].left, id, index1);
                        ^~~~~~
                        Node
prog.cpp:262:24: error: ‘nodes_’ was not declared in this scope
       int tmp = insert(nodes_[tree].right, id, index1);
                        ^~~~~~
prog.cpp:262:24: note: suggested alternative: ‘Node’
       int tmp = insert(nodes_[tree].right, id, index1);
                        ^~~~~~
                        Node
prog.cpp:268:5: error: ‘nodes_’ was not declared in this scope
     nodes_[tree].size++;
     ^~~~~~
prog.cpp:268:5: note: suggested alternative: ‘Node’
     nodes_[tree].size++;
     ^~~~~~
     Node
prog.cpp: In member function ‘void DynamicSuffixArray::split(int, int, int, int&, int&)’:
prog.cpp:290:13: error: ‘nodes_’ was not declared in this scope
       split(nodes_[tree].left, id, index1, L, nodes_[tree].left);
             ^~~~~~
prog.cpp:290:13: note: suggested alternative: ‘Node’
       split(nodes_[tree].left, id, index1, L, nodes_[tree].left);
             ^~~~~~
             Node
prog.cpp:295:13: error: ‘nodes_’ was not declared in this scope
       split(nodes_[tree].right, id, index1, nodes_[tree].right, R);
             ^~~~~~
prog.cpp:295:13: note: suggested alternative: ‘Node’
       split(nodes_[tree].right, id, index1, nodes_[tree].right, R);
             ^~~~~~
             Node

Standard output is empty